de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch
 
Hilfe Wegweiser Datenschutzhinweis Impressum Kontakt
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Zeitschriftenartikel

Improved Bounds and Schemes for the Declustering Problem

MPG-Autoren
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;

Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
Volltexte (frei zugänglich)
Es sind keine frei zugänglichen Volltexte verfügbar
Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

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


Zitierlink: http://hdl.handle.net/11858/00-001M-0000-000F-2326-D
Zusammenfassung
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.