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 among the devices. Using deep results from discrepancy theory, we improve previous work of several authors concerning rectangular queries of higher-dimensional data. For this problem, 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 not larger than the smallest prime power in the canonical decomposition of M. Thus, in particular, our schemes work for arbitrary M in two and three dimensions, and arbitrary M > d - 1 that is a power of two. These cases seem to be the most relevant in applications. For a lower bound, we show that a recent proof of a Ω_d (log d-1/2 M) bound contains a critical error. Using an alternative approach, we establish this bound.