Approximate Data Structures with Applications

Y. Matias, J. S. Vitter, and N. Young. ``Approximate Data Structures with Applications,'' Proceedings of the 5th Annual SIAM/ACM Symposium on Discrete Algorithms (SODA '94), Alexandria, VA, January 1994. The work is the basis of a patent by the authors, ``Implementation of Approximate Data Structures,'' United States Patent No. 5,519,840, Bell Laboratories, May 21, 1996.

Full text (gzip-compressed postscript)

Full text (Adobe pdf format)

In this paper we introduce the notion of approximate data structures, in which a small amount of error is tolerated in the output. Approximate data structures trade error of approximation for faster operation, leading to theoretical and practical speedups for a wide variety of algorithms. We give approximate variants of the van Emde Boas data structure, which support the same dynamic operations as the standard van Emde Boas data structure, except that answers to queries are approximate. The variants support all operations in constant time provided the error of approximation is $1/{\mathop{\rm polylog}}(n)$, and in $O(\log\log n)$ time provided the error is $1/{\mathop{\rm polynomial}}(n)$, for n elements in the data structure.

We consider the tolerance of prototypical algorithms to approximate data structures. We study in particular Prim's minimum spanning tree algorithm, Dijkstra's single-source shortest paths algorithm, and an on-line variant of Graham's convex hull algorithm. To obtain output which approximates the desired output with the error of approximation tending to zero, Prim's algorithm requires only linear time, Dijkstra's algorithm requires $O(m\log\log n)$ time, and the on-line variant of Graham's algorithm requires constant amortized time per operation.