Multidimensional Declustering Schemes Using Golden Ratio and Kronecker Sequences

We propose a new data declustering scheme, GRS, for range queries on uniform data. Our scheme is based on Golden Ratio Sequences for two dimensions and Kronecker Sequences for higher dinensions. Using exhaustive simulation we show that, in two dimensions, the worst case (additive) deviation of GRS from the optimal response time for any query is one when the numeber of disks (M) is at most 22; its worst case deviation is two when M = 94; and its worst case deviation is four when M = 550. In two dimensions, we prove that whenever M is a Fibonacci number, the average performance of GRS is within 14 percent of the (generally unachievable) strictly optimal scheme and its worst case response time is within a multiplicative factor three of the optimal response time for any query, and within a factor 1.5 of the optimal for large queries. We also present comprehensive simulation results, on two-dimensional as well as on higher-dimensional data, that compare and demonstrate the advantages of our scheme over some recently proposed schemes in the literature.