Improved Bounds and Schemes for the Declustering Problem
<|reference_start|>Improved Bounds and Schemes for the Declustering Problem: 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.<|reference_end|>
@article{doerr2006improved,
    title={Improved Bounds and Schemes for the Declustering Problem},
    author={Benjamin Doerr, Nils Hebbinghaus, S"oren Werth},
    journal={arXiv preprint arXiv:cs/0603012},
    year={2006},
    archivePrefix={arXiv},
    eprint={cs/0603012},
    primaryClass={cs.DM cs.DS}
}