Access Restriction

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

   Open content in new tab
Source: ACM Digital Library