Journal Article
@Article
Artikel in Fachzeitschrift


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:








Author, Editor(s)

Author(s):

Doerr, Benjamin
Hebbinghaus, Nils
Werth, Sören

dblp
dblp
dblp

Not MPG Author(s):

Werth, Sören

BibTeX cite key*:

ImpBoun2006

Title

Title*:

Improved Bounds and Schemes for the Declustering Problem

Journal

Journal Title*:

Theoretical Computer Science

Journal's URL:


Download URL
for the article:

http://www.sciencedirect.com/science?_ob=MImg&_imagekey=B6V1G-4JHMGY6-1-5&_cdi=5674&_user=43521&_orig=search&_coverDate=08%2F14%2F2006&_sk=996409998&view=c&wchp=dGLbVzb-zSkzk&md5=e079e8899894f7c48cb59292f5f958ea&ie=/sdarticle.pdf

Language:

English

Publisher

Publisher's
Name:

Elsevier

Publisher's URL:


Publisher's
Address:

Amsterdam, The Netherlands

ISSN:

0304-3975

Vol, No, pp, Date

Volume*:

359

Number:

1-3

Publishing Date:

2006

Pages*:

123-132

Number of
VG Pages:

14

Page Start:


Page End:


Sequence Number:


DOI:


Note, Abstract, ©

Note:


(LaTeX) 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 Mgreater-or-equal, slantedd-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.

URL for the Abstract:

http://dx.doi.org/10.1016/j.tcs.2006.02.016

Categories,
Keywords:


HyperLinks / References / URLs:


Copyright Message:


Personal Comments:


Download
Access Level:

Intranet

Correlation

MPG Unit:

Max-Planck-Institut für Informatik



MPG Subunit:

Algorithms and Complexity Group

Appearance:

MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort


BibTeX Entry:

@ARTICLE{ImpBoun2006,
AUTHOR = {Doerr, Benjamin and Hebbinghaus, Nils and Werth, S{\"o}ren},
TITLE = {Improved Bounds and Schemes for the Declustering Problem},
JOURNAL = {Theoretical Computer Science},
PUBLISHER = {Elsevier},
YEAR = {2006},
NUMBER = {1-3},
VOLUME = {359},
PAGES = {123--132},
ADDRESS = {Amsterdam, The Netherlands},
ISBN = {0304-3975},
}


Entry last modified by Christine Kiesel, 02/06/2007
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Mathias Bader
Created
11/22/2006 05:55:37 PM
Revisions
5.
4.
3.
2.
1.
Editor(s)
Christine Kiesel
Christine Kiesel
Mathias Bader
Mathias Bader
Mathias Bader
Edit Dates
06.02.2007 16:49:24
06.02.2007 16:48:40
02.01.2007 16:18:59
10.12.2006 18:51:40
24.11.2006 12:44:22