Improved Bounds and Schemes for the Declustering Problem

Details Improved Bounds and Schemes for the Declustering Problem Improved Bounds and Schemes for the Declustering Problem

2006-03-02

arxiv.org/abs/cs/0603012v1

Computer Science

Discrete Mathematics

19 pages, 1 figure

Scientific paper

The declustering problem is to allocate given data on parallel working storage devices in such a manner that typical requests find their data evenly distributed on the devices. Using deep results from discrepancy theory, we improve previous work of several authors concerning range queries to higher-dimensional data. We give a declustering scheme with an additive error of $O_d(\log^{d-1} M)$ independent of the data size, where $d$ is the dimension, $M$ the number of storage devices and $d-1$ does not exceed the smallest prime power in the canonical decomposition of $M$ into prime powers. In particular, our schemes work for arbitrary $M$ in dimensions two and three. For general $d$, they work for all $M\geq d-1$ that are powers of two. Concerning lower bounds, we show that a recent proof of a $\Omega_d(\log^{\frac{d-1}{2}} M)$ bound contains an error. We close the gap in the proof and thus establish the bound.

Affiliated with

Also associated with

No associations

Rating

Improved Bounds and Schemes for the Declustering Problem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Improved Bounds and Schemes for the Declustering Problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Improved Bounds and Schemes for the Declustering Problem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-369151