© 2003 by British Computer Society
A Hierarchical Technique for Constructing Efficient Declustering Schemes for Range Queries
1 Bell Labs, Lucent Technologies, 600 Mountain Ave, NJ 07974, USA Email: chungmin@research.telcordia.com 2 AT&T Labs - Research, 200 S. Laurel Ave., Middletown, NJ 07748, USA 3 Telcordia Technologies (formerly Bellcore), 445 South Street, Morristown, NJ 07960, USA
Multi-disk systems, coupled 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 data blocks should be placed among multiple disks to maximize the parallelism. We focus on the problem of declustering grid-structured multidimensional data with the objective of reducing the 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 times. For example we show, in two dimensions, that using optimal declustering schemes for $M_1$ and $M_2$ disks we can construct a scheme for $M_1\times M_2$ disks whose response time, expressed in terms of the maximum number of data blocks to be retrieved from any of the disks, 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.
Received 3 June, 2002. Revised 27 December, 2002.