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 prune 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.