James Aspnes, David Eisenstat, and Yitong Yin. Low contention data structures. In preparation.
We consider the problem of minimizing contention in static dictionary data structures, where the contention on each cell is measured by the expected number of probes to that cell given an input that is chosen from a distribution that is not known to the query algorithm (but that may be known when the data structure is built). When all positive queries are equally probable, and similarly all negative queries are equally probable, we show that it is possible to construct a data structure using linear space s, a constant number of queries, and with contention O(1/s) on each cell, corresponding to a nearly-flat load distribution. All of these quantities are asymptotically optimal. For arbitrary query distributions, we give a general method for transforming any data structure to a low-contention one, at the cost of O(log n/log log n)$ time and space overhead. The lack of knowledge of the query distribution by the query algorithm prevents perfect load leveling in this case: we present a lower bound, based on VC-dimension, that shows that for a wide range of data structure problems, achieving contention even within a polylogarithmic factor of optimal requires a cell-probe complexity of Ω(log log n).
@unpublished{AspnesEY2009,
author = {James Aspnes and David Eisenstat and Yitong Yin},
title = {Low-contention data structures},
month=sep,
year = 2009,
note = {Unpublished manuscript}
}