A Hierarchical Technique for Constructing Efficient Declustering Schemes for Range Queries

Multi-disk systems, coupling with declustering schemes, have been widely used in various applications to improve I/O performance by enabling parallel disk accesses. A declustering scheme determines how to place data blocks among multiple disks to maximize the parallelism. We focus on the problem of declustering grid-structured multidimensional data with the objective to reduce response time for range queries. Because of the combinatorial nature of the problem, it is not computationally feasible to perform an exhaustive search for the best scheme for large values of M (the number of disks). In this paper, we present an efficient technique for building good-performance declustering schemes for large values of M, based on known good declustering schemes for small values of M. We analyze the performance of the declustering schemes generated by this hierarchical technique, giving tight bounds on their query response time. For example we show, in two dimensions, that using optimal declustering schemes for M1 and M2 disks we can construct a scheme for M1 x M2 disks whose response time is at most five more than the optimal response time. Our technique generalizes to any value of M in two dimensions and selected values of M in higher dimensions. We also present simulation results to show the effectiveness of these schemes in practice.