Computer Science – Data Structures and Algorithms
Scientific paper
2002-05-10
ACM-SIAM Symposium on Discrete Algorithms, 1994
Computer Science
Data Structures and Algorithms
Scientific paper
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(loglogn) time provided the performance guarantee is 1+1/polynomial(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(mloglogn) time, and the on-line variant of Graham's algorithm requires constant amortized time per operation.
Matias Yossi
Vitter Jeff
Young Neal
No associations
LandOfFree
Approximate Data Structures with Applications does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Approximate Data Structures with Applications, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Approximate Data Structures with Applications will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-382476