Probabilistic Counting Algorithms for Data Base Applications
📜 Abstract
This paper introduces a class of probabilistic counting algorithms with which one can estimate the number of distinct elements in a large collection of data (typically a large file stored on disk) in a single pass using only a small additional storage (typically less than a hundred binary words) and only a few operations per element scanned. The algorithms are based on statistical observations made on bits of hashed values of records. They are by construction totally insensitive to the replicative structure of elements in the file; they can be used in the context of distributed systems without any degradation of performances and prove especially useful in the context of data bases query optimisation.
✨ Summary
The paper establishes the Flajolet–Martin approach to distinct-cardinality estimation: hashed bit patterns are recorded in compact bitmaps, and the position of the first zero provides an estimate whose logarithm is related to the number of distinct elements. It develops the probability distribution, bias, variance, and asymptotic behavior of the estimator, then introduces probabilistic counting with stochastic averaging (PCSA), which reduces error approximately in proportion to the inverse square root of the number of bitmaps while retaining one-pass, low-storage processing.
The work became an early foundation for streaming sketches and approximate query processing. Subsequent research developed LogLog and HyperLogLog estimators from the same general principles; HyperLogLog is described as a later cardinality-estimation algorithm based on this line of work. (datasketches.apache.org) HyperLogLog-style estimators have also been used in production-scale data systems, including Google’s PowerDrill and Presto. (research.google.com) The original PCSA method has additionally been implemented as a PostgreSQL extension for approximate distinct-value aggregation. (pgxn.org)