Approximate data structures with applications

In this paper we introduce the notion of approximate da2a siruclures, 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.

• Publication year

  1994

• Venue

  ACM-SIAM Symposium on Discrete Algorithms

• Publication date

  1994-01-23

• Fields of study

  Mathematics, Computer Science

• Identifiers
  arXiv cs/0205010
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Dynamic Generation of Discrete Random Variates

  1993cited by this paper
• Polynomial Hash Functions Are Reliable (Extended Abstract)

  1992cited by this paper
• Applications of the fusion tree method to computational geometry and searching

  1992cited by this paper
• On maintaining the width and diameter of a planar point-set online

  1991cited by this paper
• Numerical stability of algorithms for line arrangements

  1991cited by this paper
• A New Universal Class of Hash Functions and Dynamic Hashing in Real Time

  1990cited by this paper
• Trans-dichotomous algorithms for minimum spanning trees and shortest paths

  1990cited by this paper
• BLASTING through the information theoretic barrier with FUSION TREES

  1990cited by this paper
• Calculating approximate curve arrangements using rounded arithmetic

  1989cited by this paper
• Fast geometric approximation techniques and geometric embedding problems

  1989cited by this paper
• Epsilon geometry: building robust algorithms from imprecise computations

  1989cited by this paper
• Double precision geometry: a general technique for calculating line and segment intersections using rounded arithmetic

  1989cited by this paper
• Stable maintenance of point set triangulations in two dimensions

  1989cited by this paper
• Verifiable Implementations of Geometric Algorithms Using Finite Precision Arithmetic

  1989cited by this paper
• Finite-resolution computational geometry

  1986cited by this paper
• Data Structures and Algorithms

  1983cited by this paper
• Data structures and network algorithms

  1983influential reference
• Upper Bounds for Sorting Integers on Random Access Machines

  1981cited by this paper
• An optimal real-time algorithm for planar convex hulls

  1979cited by this paper
• The Design and Analysis of Computer Algorithms

  1974influential reference
• An Efficient Algorithm for Determining the Convex Hull of a Finite Planar Set

  1972influential reference
• A note on two problems in connexion with graphs

  1959influential reference
• Shortest connection networks and some generalizations

  1957influential reference

• MQF and buffered MQF: quotient filters for efficient storage of k-mers with their counts and metadata

  2020cites this paper
• Evaluating Lossy Collections for Java Applications

  2015cites this paper
• Computing Discriminating and Generic Words

  2012cites this paper
• Data Structures for Approximate Orthogonal Range Counting

  2009cites this paper
• Data Structures for Approximate Range Counting

  2009cites this paper
• Dynamic Coresets

  2008cites this paper
• Determining the Visibility of a Planar Set of Line Segments in O(n log log n) Time

  2007cites this paper
• A growing functional module designed to trigger causal inference

  2007cites this paper
• Workload-Based Wavelet Synopses

  2005cites this paper
• Adaptive sampling for geometric problems over data streams

  2004cites this paper
• Time-Interval Sampling for Improved Estimations in Data Warehouses

  2002cites this paper
• Optimal static range reporting in one dimension

  2001cites this paper
• Join synopses for approximate query answering

  1999cites this paper
• Approximate Indexed Lists

  1998cites this paper
• System and Techniques for Approximate Query Answering

  1998cites this paper
• New sampling-based summary statistics for improving approximate query answers

  1998cites this paper
• Car-Pooling as a Data Structuring Device: The Soft Heap

  1998cites this paper
• Neural networks for convex hull computation

  1997cites this paper
• Dynamic Generation of Discrete Random Variates 1

  1997cites this paper
• Aqua Project White Paper

  1997cites this paper
• Performance evaluation of approximate priority queues

  1996cites this paper
• The Optimal Alphabetic Tree Problem Revisited

  1994cites this paper
• Optimal parallel approximation for prefix sums and integer sorting

  1994cites this paper
• B.3 Dynamic Hashing Figure 6: Rejection Method B.1 Rejection Method

  1993cites this paper
• Dynamic Generation of Discrete Random Variates

  1993cites this paper