Loading...
Approximate Data Structures with Applications
Matias, Yossi Vitter, Jeffrey Scott Young, Neal E.
Matias, Yossi
Vitter, Jeffrey Scott
Young, Neal E.
Citations
Altmetric:
Abstract
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 [28, 201, except that answers to queries are approximate. The variants support all operations in constant time provided the error of approximation is l/polylog(n), and in O(loglog n) time provided the error
is l/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 minimumspanning 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(mloglogn) time, and the on-line variant of Graham’s algorithm requires constant amortized time per operation.
Description
Date
1994
Journal Title
Journal ISSN
Volume Title
Publisher
Society for Industrial and Applied Mathematics
Research Projects
Organizational Units
Journal Issue
Keywords
Citation
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, 361–370.