MEAN-VARIANCE ANALYSIS OF THE PERFORMANCE OF SPATIAL ORDERING METHODS

Geographical Information Systems (GIS) involve the manipulation of lar ge spatial data sets, and the performance of these systems is often de termined by how these data sets are organized on secondary storage (di sk). This paper describes a simulation study investigating the perform ance of two non-recursive spatial clustering methods-the Inverted Naiv e and the Spiral methods-in extensive detail and comparing them with t he Hilbert fractal method that has been shown in previous studies to o utperform other recursive clustering methods. The paper highlights the importance of analysing the sample variance when evaluating the relat ive performance of various spatial ordering methods. The clustering pe rformance of the methods is examined in terms of both the mean and var iance values of the number of clusters (runs of consecutive disk block s) that must be accessed to retrieve a query region of a given size an d orientation. The results show that, for a blocking factor of 1, the mean values for the Spiral method are the best, and on average, about 30% better than for the other two methods. In terms of variance, the i nverted naive method is the best followed by the Spiral and Hilbert me thods, in that order. We also study the impact of varying query size a nd the skew ratio (between the X and Y dimensions) for each method. Wh ile these performance results do not generalize for higher blocking fa ctors, we believe that they are useful for both researchers and practi tioners to know because several previous studies have also examined th is special case, and also because it has important implications for th e performance of GIS applications.