Improved bounds and schemes for the declustering problem
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 >= d - 1 that are powers of two. Concerning lower bounds, we show that a recent proof of a Omega(d)(log((d-1)/2)M) bound contains an error. We close the gap in the proof and thus establish the bound. (C) 2006 Elsevier B.V. All rights reserved.
declustering discrepancy hypergraph coloring