Low-contention data structures

We consider the problem of minimizing contention in static (read-only) dictionary data structures, where contention is measured with respect to a fixed query distribution by the maximum expected number of probes to any given cell. The query distribution is known by the algorithm that constructs the data structure but not by the algorithm that queries it. Assume that the dictionary has nn items. When all queries in the dictionary are equiprobable, and all queries not in the dictionary are equiprobable, we show how to construct a data structure in O(n)O(n) space where queries require O(1)O(1) probes and the contention is O(1/n)O(1/n). Asymptotically, all of these quantities are optimal. For arbitrary   query distributions, we construct a data structure in O(n)O(n) space where each query requires O(logn/loglogn)O(logn/loglogn) probes and the contention is O(logn/(nloglogn))O(logn/(nloglogn)). The lack of knowledge of the query distribution by the query algorithm prevents perfect load leveling in this case: for a large class of algorithms, 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 Ω(loglogn)Ω(loglogn).

► Cell-probe model with a measure of contention.
► Dictionary with O(1)O(1) probes, O(n)O(n) space, and O(1/n)O(1/n) contention for uniform queries.
► O(logn/loglogn)O(logn/loglogn) probes, O(logn/nloglogn)O(logn/nloglogn) contention in general.
► VC-dimension shows Ω(loglogn)Ω(loglogn) probes needed for polylog contention.