Linear Counting Distinct Bitmap
Estimate distinct keys from unoccupied hash buckets and recognize saturation.
Free theory articleEstimate distinct keys from unoccupied hash buckets and recognize saturation.
Concept & interpretation
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.
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.