A statistical analysis of probabilistic counting algorithms
From MaRDI portal
Abstract: This paper considers the problem of cardinality estimation in data stream applications. We present a statistical analysis of probabilistic counting algorithms, focusing on two techniques that use pseudo-random variates to form low-dimensional data sketches. We apply conventional statistical methods to compare probabilistic algorithms based on storing either selected order statistics, or random projections. We derive estimators of the cardinality in both cases, and show that the maximal-term estimator is recursively computable and has exponentially decreasing error bounds. Furthermore, we show that the estimators have comparable asymptotic efficiency, and explain this result by demonstrating an unexpected connection between the two approaches.
Recommendations
- Probabilistic counting algorithms for data base applications
- scientific article; zbMATH DE number 5763313
- Order statistics and estimating cardinalities of massive data sets
- Order statistics and estimating cardinalities of massive data sets
- Advances in Computer Science - ASIAN 2004. Higher-Level Decision Making
Cites work
- A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
- A result in order statistics related to probabilistic counting
- An improved data stream summary: the count-min sketch and its applications
- Data streams. Models and algorithms.
- Data streams: algorithms and applications.
- scientific article; zbMATH DE number 3473265 (Why is no real title available?)
- scientific article; zbMATH DE number 2019620 (Why is no real title available?)
- scientific article; zbMATH DE number 3349081 (Why is no real title available?)
- scientific article; zbMATH DE number 3060913 (Why is no real title available?)
- scientific article; zbMATH DE number 3063453 (Why is no real title available?)
- Linear Statistical Inference and its Applications
- LogLog counting of large cardinalities (extended abstract)
- Numerical calculation of stable densities and distribution functions
- Numerical recipes. The art of scientific computing.
- Order statistics and estimating cardinalities of massive data sets
- Probabilistic counting algorithms for data base applications
- Pseudorandom generators for space-bounded computation
- Stable distributions, pseudorandom generators, embeddings, and data stream computation
- The space complexity of approximating the frequency moments
- Universal classes of hash functions
Cited in
(17)- Probabilistic counting algorithms for data base applications
- An analysis of Monte Carlo algorithms for counting problems
- A result in order statistics related to probabilistic counting
- Winograd's algorithm statistically revisited: it pays to weigh than to count!
- Data streams as random permutations: the distinct element problem
- An optimal cardinality estimation algorithm based on order statistics and its full analysis
- Distinct counting with a self-learning bitmap
- scientific article; zbMATH DE number 4162272 (Why is no real title available?)
- Approximate counting with a floating-point counter
- scientific article; zbMATH DE number 4030785 (Why is no real title available?)
- A statistical analysis of the towers of hanoi problem
- On distributed cardinality estimation: random arcs recycled
- A framework for estimating stream expression cardinalities
- Advances in Computer Science - ASIAN 2004. Higher-Level Decision Making
- Order statistics and estimating cardinalities of massive data sets
- Cardinality estimation using Gumbel distribution
- Optimizing the confidence bound of count-min sketches to estimate the streaming big data query results more precisely
This page was built for publication: A statistical analysis of probabilistic counting algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2911701)
