Improved Bounds and Schemes for the Declustering Problem
| dc.creator | Doerr, Benjamin | |
| dc.creator | Hebbinghaus, Nils | |
| dc.creator | Werth, Sören | |
| dc.date | 2006-03-02 | |
| dc.date.accessioned | 2026-07-07T07:05:46Z | |
| dc.date.available | 2026-07-07T07:05:46Z | |
| dc.description | 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 $Ω_d(\log^{\frac{d-1}{2}} M)$ bound contains an error. We close the gap in the proof and thus establish the bound. | |
| dc.description | 19 pages, 1 figure | |
| dc.identifier | https://arxiv.org/abs/cs/0603012 | |
| dc.identifier | http://arxiv.org/abs/cs/0603012 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/109785 | |
| dc.subject | Discrete Mathematics | |
| dc.subject | Data Structures and Algorithms | |
| dc.subject | G.2.2; E.1 | |
| dc.title | Improved Bounds and Schemes for the Declustering Problem | |
| dc.type | text |