From Discrepancy to Declustering: Near-Optimal Multidimensional Declustering Strategies for Range Queries

摘要

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 data blocks of the query stored by the scheme in any one of the disks. If |Q| is the number of data blocks 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 a set of range queries Q is to measure its additive error-the maximum difference of rt(Q) from [｜Q｜/M] over all range queries Q ∈ Q. In this article, we consider the problem of designing declustering schemes for uniform multidimensional data arranged in a d-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 dimension d ≥ 2, any declustering scheme on an M~d grid, a grid with length M on each dimension, will always incur an additive error with respect to range queries of Ω(log M) when d = 2 and Ω(log~((d-1)/2)M) when d > 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 of d-dimensional declustering schemes, d ≥ 3, is O(M~(d-1)), which is large when compared to the lower bound. In this article, we propose two declustering schemes based on low-discrepancy points in d-dimensions. When d is fixed, both schemes have an additive error of O(log~(d-1)M) 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 in M, while the second scheme requires d ≥ 2 and M = p~t where d ≤ p ? C, C a constant, and t is a positive integer such that t(d - 1) ≥ 2. These are the first multidimensional declustering schemes with additive errors proven to be near optimal.