Declustering using golden ratio sequences

Abstract

We propose a new data declustering scheme for range queries. Our scheme is based on Golden Ratio Sequences (GRS), which have found applications in broadcast disks, hashing, packet routing, etc. We show by analysis and simulation that GRS is nearly the best possible scheme for 2-dimensional range queries. Specifically, it is the best possible scheme when the number of disks (M) is at most 22; has response time at most one more than that of the best possible scheme for M/spl les/94; and has response time at most three more than that of the best possible scheme for M/spl les/550. We also show that it outperforms the cyclic declustering scheme-a recently proposed scheme that was shown to have better performance than previously known schemes for this problem. We give some analytical results to suggest that the average performance of our scheme is within 14 percent of the optimal scheme. Our analytical results also suggest a worst case response time within a factor 3 of the optimal for any query, and within a factor 1.5 of the optimal for large queries. We also give a multidimensional extension of our scheme, which has better performance than the multidimensional generalization of the cyclic declustering scheme.