Linear Counting Distinct Bitmap

Linear counting provides a way to estimate the cardinality (number of distinct elements) of a multiset using a fixed-size bitmap. It works by observing how many bits remain unset after hashing the stream of items.

Theory

Given a bitmap of size m initialized to all zeros, each item in a data stream is hashed to a uniform random integer, modulo m. The bit at the resulting index is set to 1. Multiple occurrences of the same distinct item will hash to the same index, having no further effect on the bitmap.

Assuming an ideal uniform hash function, the probability that a specific bucket remains empty after n distinct elements are inserted is (1 - 1/m)^n. For large m, this approximates e^(-n/m). Let V be the number of empty buckets. We expect V/m ≈ e^(-n/m). By rearranging, the estimated cardinality hat(n) is:

hat(n) = -m ln(V/m)

Worked Example

Let us calculate the estimated distinct count for a scenario where we have a bitmap of size m = 16 and after processing a stream of elements, we find exactly 8 empty buckets. Since 8 buckets are empty, the ratio of empty buckets is 8 / 16 = 0.5. We plug these values into the linear counting estimator formula.

Identify parameters: m = 16, V = 8.
Calculate ratio: V/m = 8 / 16 = 0.5.
Take the natural logarithm: ln(0.5) ≈ -0.693147.
Multiply by -m: -16 × -0.693147 ≈ 11.090354888959125.

Thus, the estimated number of distinct elements is approximately 11.09. Notice that collisions cause the estimate to be higher than the true distinct keys (8) if the keys were perfectly uniformly distributed without collisions.

Experiment

In the interactive Linear Counting Distinct Bitmap module, you can visualize keys hashing into the bitmap:

Set Stream to "Distinct" and observe the occupied buckets.
Change Stream to "Repeated" and notice the occupied bucket count does not change, keeping the estimate stable.
Change Hash to "Clustered" and observe how clustering causes higher collisions, degrading the estimated count.

Limitations

Linear counting relies on the assumption of uniformly distributed hash outputs. If the hash function clusters outputs (as demonstrated by the "Clustered" option in the interactive module), the number of empty buckets will be artificially high, leading to significant underestimation of the true cardinality.

Furthermore, the estimator saturates when all buckets are occupied (V = 0). When this happens, the natural logarithm is undefined (resulting in infinity), and the algorithm can no longer provide a finite estimate. For very large streams, the bitmap size m must be sufficiently large, or more space-efficient algorithms like HyperLogLog should be used.

References

The concept of linear counting relies on probabilistic analysis of bitmap saturation under uniform hashing. Primary sources include early literature on database management and cardinality estimation techniques, establishing the expected fraction of empty buckets.

Whang, K.-Y., Vander-Zanden, B. T., & Taylor, H. M. (1990). A Linear-Time Probabilistic Counting Feature for Database Applications. ACM Transactions on Database Systems, 15(2), 208-229.Read paper

Linear Counting Distinct Bitmap