### From discrepancy to declustering: Near-optimal multidimensional declustering strategies for range queriesFrom discrepancy to declustering: Near-optimal multidimensional declustering strategies for range queries

Access Restriction
Subscribed

 Author Chen, Chung-Min ♦ Cheng, Christine T. Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2004 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Declustering schemes ♦ Disk allocations ♦ Parallel database ♦ Range query Abstract Declustering schemes allocate data blocks among multiple disks to enable parallel retrieval. Given a declustering scheme $\textit{D},$ its response time with respect to a query $\textit{Q},$ $\textit{rt}(\textit{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 $|\textit{Q}|$ is the number of data blocks in $\textit{Q}$ and $\textit{M}$ is the number of disks, then $\textit{rt}(\textit{Q})$ is at least $⌈|\textit{Q}|/\textit{M}⌉.$ One way to evaluate the performance of $\textit{D}$ with respect to a set of range queries Q is to measure its additive error---the maximum difference of $\textit{rt}(\textit{Q})$ from $⌈|\textit{Q}|/\textit{M}⌉$ over all range queries $\textit{Q}$ ∈ Q.In this article, we consider the problem of designing declustering schemes for uniform multidimensional data arranged in a $\textit{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 $\textit{d}$ ≥ 2, any declustering scheme on an $M^{d}$ grid, a grid with length $\textit{M}$ on each dimension, will always incur an additive error with respect to range queries of Ω(log $\textit{M})$ when $\textit{d}$ = 2 and $Ω(log^{d™1/2}$ $\textit{M})$ when $\textit{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 $\textit{d}-dimensional$ declustering schemes, $\textit{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 $\textit{d}-dimensions.$ When $\textit{d}$ is fixed, both schemes have an additive error of $O(log^{d™1}$ $\textit{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 $\textit{M},$ while the second scheme requires $\textit{d}$ ≥ 2 and $\textit{M}$ = $p^{t}$ where $\textit{d}$ ≤ $\textit{p}$ ≤ $\textit{C},$ $\textit{C}$ a constant, and $\textit{t}$ is a positive integer such that $\textit{t}(\textit{d}$ ™ 1) ≥ 2. These are the first multidimensional declustering schemes with additive errors proven to be near optimal. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2004-01-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 51 Issue Number 1 Page Count 28 Starting Page 46 Ending Page 73

#### Open content in new tab

Source: ACM Digital Library