From Discrepancy to Declustering:  Near-optimal multidimensional declustering strategies for range queries

 

Abstract

With improvements in computer processing speed and storage capabilities, disk I/O (input/output) has become the bottleneck for many modern data-intensive applications.  As such, the use of multi-disk systems together with declustering schemes has been suggested.  Declustering schemes allocate data blocks among multiple disks to enable parallel retrieval. Given a declustering scheme D, its response time with respect to a query Q,  rt(Q), is defined to be the maximum number of disk blocks of the query stored by the scheme in any one of the disks.  If |Q| is the number of tiles in Q and M is the number of disks then rt(Q) is at least |Q|/M.  One way to evaluate the performance of D with respect to range queries is to measure its  additive error - the  maximum difference between rt(Q) and |Q|/M over all range queries Q. In this talk, I will present two declustering schemes for uniform multidimensional data arranged in a d-dimensional grid.  These schemes are the first known declustering schemes whose asymptotic additive errors with respect to range queries are near optimal.