A declustering scheme with guaranteed worst-case additive error O(k1(d-1)/) for d-dimensional range queries

Declustering schemes for range queries have been widely used in parallel storage systems to allow fast access to multidimensional data. A declustering scheme distributes data blocks among several devices (e.g., disks) so that the number of parallel block accesses needed per query is minimized. Given a system of k disks, a query that accesses m blocks needs a number of parallel block accesses that is at least OPT=┌m/k┐. In literature, the performance of any declustering scheme is measured by its worst-case additive deviation from OPT. A number of asymptotically optimal declustering schemes are known for 2-dimensional range queries. The case of higher dimensions appears intrinsically very difficult. None of the proposed schemes provide any non-trivial performance guarantees in higher dimensions. In this paper, we describe a declustering scheme which has guaranteed worst-case performance of OPT+O(k¹(d-1)/) parallel block accesses for d dimensions. Our scheme is a generalization of a 2-dimensional scheme proposed by Atallah and Prabhakar in 2000.