DataSketches.Distinct.HyperLogLog

HyperLogLog sketch for cardinality (distinct count) estimation.

"How many different things have I seen?" — not how many total, but how many unique. Think unique visitors, unique IPs, unique search queries. Counting exactly requires remembering every item you've seen (a set), which grows with the data. HyperLogLog answers the same question using a few kilobytes, no matter how large the stream.

It works by hashing each item and tracking the maximum number of leading zeros observed across 2^p independent register buckets.

The standard error is approximately 1.04 / sqrt(2^p).

Precision configurations

+------+-----------+------+-------------+ | p | Registers | RAM | Std. error | +======+===========+======+=============+ | 10 | 1,024 | 1 KB | ~3.25% | +------+-----------+------+-------------+ | 12 | 4,096 | 4 KB | ~1.63% | +------+-----------+------+-------------+ | 14 | 16,384 | 16 KB| ~0.81% | +------+-----------+------+-------------+ | 16 | 65,536 | 64 KB| ~0.41% | +------+-----------+------+-------------+

Hashing

Items must be pre-hashed to Word64. Apply a good hash function (e.g. from hashable or xxhash) to your domain types before calling insert. The quality of the cardinality estimate depends on the hash being uniform.

Implementation

Backed by a C implementation (cbits/hll.c) behind a ForeignPtr. All sketch memory lives outside the GHC heap.

Usage

import qualified DataSketches.Distinct.HyperLogLog as HLL
import Data.Hashable (hash)

main :: IO ()
main = do
  sk <- HLL.mkHllSketch 12
  mapM_ (HLL.insert sk . fromIntegral . hash) ["alice", "bob", "alice"]
  n <- HLL.estimate sk
  putStrLn $ "distinct count ≈ " ++ show n  -- ≈ 2.0

Mergeability

Fully mergeable via merge. The union of two HLL sketches gives the same result as inserting all items from both streams into a single sketch. Both must share the same precision p.

When to use Theta instead

HyperLogLog only supports cardinality estimation and union. If you need set intersection or difference, use DataSketches.Distinct.Theta.