Approximate Data Structures with Applications (Extended Abstract)

) Yossi Matias y Jeffrey Scott Vitter z Neal E. Young x 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, 20], except that answers to queries are approximate. The variants support all operations in constant time provided the error of approximation is 1=polylog(n), and in O(log log n) time provided the error is 1=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 varia..