Everything about Approximate counting algorithm
Optimization theory in computing
The approximate counting algorithm allows the counting of a large number of events using a small amount of memory. Invented in 1977 by Robert Morris of Bell Labs, it uses probabilistic techniques to increment the counter. It was fully analyzed in the early 1980s by Philippe Flajolet of INRIA Rocquencourt, who coined the name approximate counting, and strongly contributed to its recognition among the research community. When focused on high quality of approximation and low probability of failure, Nelson and Yu showed that a very slight modification to the Morris Counter is asymptotically optimal amongst all algorithms for the problem. The algorithm is considered one of the precursors of streaming algorithms, and the more general problem of determining the frequency moments of a data stream has been central to the field. Wikipedia →
🧠Start here: a 6-step reading path
- Read the overview: Approximate counting algorithmA 5-minute orientation
- Pick up a classic book: Introduction to AlgorithmsThe most-reprinted book on the subject
- Read the landmark paper: An algorithm for approximate counting using limited memory resourcesCited 9 times
- Go sideways: HyperLogLogA closely related topic
- Go sideways: Streaming algorithmA closely related topic
đź“– Definitions
No dictionary entry for this exact phrase.
🗂️ The subject at a glance
🏆 Landmark papers (most cited)
đź“š Books worth reading
Introduction to AlgorithmsThomas H. Cormen, Charles E. Leiserson · 1990- 📕Applied data miningGuandong Xu · 2013
Randomized AlgorithmsRuss Bubley · 2000
Experimental AlgorithmsVincenzo Bonifaci · 2013
Similarity-Based Pattern RecognitionEdwin Hancock · 2013
Discrete mathematicsLászló Lovász, Jozsef Pelikan · 2003
Linguistic structure predictionNoah A. Smith · 2011
Subset selection in regressionMiller, Alan J. · 1990
Ranked by number of editions on Open Library, a rough measure of how lasting a book is.
đź”— Related topics
- HyperLogLog HyperLogLog is an algorithm for the count-distinct problem, approximating the number of distinct elements in a multiset. Calculating the exact cardinality…
- Streaming algorithm In computer science, streaming algorithms process input data streams as a sequence of items, typically making just one pass (or a few passes) through the…
- Bloom filter In computing, a Bloom filter is a space-efficient probabilistic data structure, conceived by Burton Howard Bloom in 1970, that is used to test whether…
- Quantum counting algorithm The Quantum counting algorithm is a quantum algorithm for efficiently counting the number of solutions for a given search problem. The algorithm is based…
- Randomized rounding In computer science and operations research, randomized rounding is a widely used approach for designing and analyzing approximation algorithms. Many combinator…
- Law of the iterated logarithm In probability theory, the law of the iterated logarithm describes the magnitude of the fluctuations of a random walk. The original statement of the law…
- Linear programming relaxation In mathematics, the relaxation of a (mixed) integer linear program is the problem that arises by removing the integrality constraint of each variable.…
- Yao's principle In computational complexity theory, Yao's principle (also called Yao's minimax principle or Yao's lemma) relates the performance of randomized algorithms…