neal young / Matias94Approximate
-
This paper explores the notion of approximate data
structures, which return approximately correct
answers to queries, but run faster than their exact
counterparts. The paper describes approximate variants of the
van Emde Boas data structure, which support the same dynamic
operations as the standard van Emde Boas data structure (min,
max, successor, predecessor, and existence queries, as well as
insertion and deletion), except that answers to queries are
approximate. The variants support all operations in constant
time provided the performance guarantee is 1+1/polylog n, and
in O(log log n) time provided the performance guarantee is
1+1/poly(n), for n elements in the data structure.
Applications described include 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 performance guarantee tending to 1, 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.
© Copyrights are reserved by the publishers.
Download for personal and limited academic use only.