Declustering Using Golden Ratio Sequences

In this paper, 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. GRS are highly regular sequences, in which elements of certain sets are almost uniformly distributed. For declustering 2-dimensional data among M disks, our scheme has the properties that (1) no two data points within any row or column of length M get assigned to the same disk, and (2) the data points which get assigned to the same disk are selected based on GRS. These properties ensure that the data points in any rectangular query within the grid have a nearly uniform distribution on the M disks. We show, by simulation, that our scheme outperforms the cyclic declustering scheme - a recently proposed scheme that was shown to have better performance than previously known schemes for this problem. We also give some analytical results to suggest that the average performance of our scheme be within 20 percent of the optimal scheme and for M >= 55 we can show that the performance improves to 14 percent.