de.mpg.escidoc.pubman.appbase.FacesBean
English
 
Help Guide Disclaimer Contact us Login
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Journal Article

Improved Bounds and Schemes for the Declustering Problem

MPS-Authors
http://pubman.mpdl.mpg.de/cone/persons/resource/persons44338

Doerr,  Benjamin
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons44598

Hebbinghaus,  Nils
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Locator
There are no locators available
Fulltext (public)
There are no public fulltexts available
Supplementary Material (public)
There is no public supplementary material available
Citation

Doerr, B., Hebbinghaus, N., & Werth, S. (2006). Improved Bounds and Schemes for the Declustering Problem. Theoretical Computer Science, 359, 123-132.


Cite as: http://hdl.handle.net/11858/00-001M-0000-000F-2326-D
Abstract
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 Od(logd-1M) 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 Md-1 that are powers of two. Concerning lower bounds, we show that a recent proof of a Ωd(log(d-1)/2M) bound contains an error. We close the gap in the proof and thus establish the bound.