Abstract
Declustering schemes allocate data blocks among multiple disks to enable parallel retrieval. Given a declustering schemeD, itsresponse timewith respect to a queryQ,rt(Q), is defined to be the maximum number of data blocks of the query stored by the scheme in any one of the disks. If |Q| is the number of data blocks inQandMis the number of disks, thenrt(Q) is at least ⌈|Q|/M⌉. One way to evaluate the performance ofDwith respect to a set of range queries Q is to measure itsadditive error---the maximum difference ofrt(Q) from ⌈|Q|/M⌉ over all range queriesQ∈ Q.In this article, we consider the problem of designing declustering schemes for uniform multidimensional data arranged in ad-dimensional grid so that their additive errors with respect to range queries are as small as possible. It has been shown that for a fixed dimensiond≥ 2, any declustering scheme on anMdgrid, a grid with lengthMon each dimension, will always incur an additive error with respect to range queries of Ω(logM) whend= 2 and Ω(logd−1/2M) whend> 2.Asymptotically optimal declustering schemes exist for 2-dimensional data. However, the best general upper bound known so far for the worst-case additive errors ofd-dimensional declustering schemes,d≥ 3, isO(Md−1), which is large when compared to the lower bound. In this article, we propose two declustering schemes based on low-discrepancy points ind-dimensions. Whendis fixed, both schemes have an additive error ofO(logd−1M) with respect to range queries, provided that certain conditions are satisfied: the first scheme requires that the side lengths of the grid grow at a rate polynomial inM, while the second scheme requiresd≥ 2 andM=ptwhered≤p≤C,Ca constant, andtis a positive integer such thatt(d− 1) ≥ 2. These are the first multidimensional declustering schemes with additive errors proven to be near optimal.

This publication has 20 references indexed in Scilit: