hide
Free keywords:
-
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.
