# Low contention data structures

James Aspnes, David Eisenstat, and Yitong Yin.
Low contention data structures.
*Journal of Parallel and Distributed Computing*, 72(5):705–715, May 2012.
An earlier version appeared in
Twenty-Second ACM Symposium on Parallelism in Algorithms and
Architectures, June 2010, pp. 345–354.

## Abstract

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 n 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) space where queries require $O(1)$ probes
and the contention is O(1/n).
Asymptotically, all of these quantities are optimal.
For *arbitrary* query distributions,
we construct a data structure in O(n) space where each query requires O(log n / log log n) probes and the contention is O(log n / (n log log n)).
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 Ω(log log n).

- SPAA 2010 proceedings version: PDF.
- JPDC version:
**PDF**.

## BibTeX

Download@article{AspnesEY2012,
author = {James Aspnes and David Eisenstat and Yitong Yin},
title = {Low-contention data structures},
month=may,
year = 2012,
journal={Journal of Parallel and Distributed Computing},
volume=72,
number=5,
pages = {705--715}
}

Consolidated BibTeX file

Return to James Aspnes's publications

Return to James Aspnes's home page