sml-hyperloglog

HyperLogLog: a probabilistic sketch for estimating the cardinality (number of distinct elements) of a multiset, in pure Standard ML.

Hash each item to a uniformly-distributed 64-bit value; use the first p bits to pick one of 2^p registers, and count the leading zeros in the rest of the hash (plus one) as an observation of a geometric random variable. Each register keeps only the maximum observation ever seen; the harmonic mean of 2^register across all registers, scaled by a bias constant, gives a cardinality estimate using 2^p small counters instead of storing the set itself. This implementation follows the original Flajolet, Fusy, Gandouet & Meunier (2007) algorithm with small-range linear-counting correction.

No dependencies, no FFI, no threads, no clock, no randomness: the same inputs always produce the same outputs under MLton and Poly/ML. Hashing uses a dependency-free internal 64-bit FNV-1a followed by a MurmurHash3-style fmix64 finalizer (see "Hashing" below for why the finalizer is required). add and merge are persistent: every call returns a new sketch and never mutates its argument.

API

signature HYPERLOGLOG =
sig
  type t

  val empty     : int -> t          (* precision p in [4,16]; 2^p registers *)
  val precision : t -> int
  val size      : t -> int          (* 2^(precision t) *)
  val add       : t -> string -> t
  val estimate  : t -> real
  val merge     : t * t -> t        (* register-wise max; requires equal precision *)
end

Example

val sk  = List.foldl (fn (s, acc) => Hyperloglog.add acc s)
                      (Hyperloglog.empty 14)
                      (List.tabulate (1000, fn i => Int.toString i))
val est = Hyperloglog.estimate sk        (* ~1000, within a few percent *)

val a = Hyperloglog.add (Hyperloglog.empty 14) "x"
val b = Hyperloglog.add (Hyperloglog.empty 14) "y"
val u = Hyperloglog.merge (a, b)          (* estimate ~ 2 *)

Running examples/demo.sml with make example prints:

HyperLogLog (p = 14, 16384 registers):
  1000 distinct items    -> estimate 1003.09
  same item added 500x   -> estimate 1.00

Merge (disjoint sets, 500 + 500 distinct items):
  estimate(A)             = 496.45
  estimate(B)             = 501.60
  estimate(merge(A,B))    = 995.65

Merge (overlapping sets, [0,600) and [300,900), true union = 900):
  estimate(C)             = 599.85
  estimate(D)             = 601.92
  estimate(merge(C,D))    = 905.57

Accuracy

HyperLogLog is a probabilistic sketch, not an exact counter. For precision p (i.e. m = 2^p registers), the estimator's relative standard error is approximately:

1.04 / sqrt(m)

For p = 14 (m = 16384), that is about 0.81% — in practice, repeated estimates for the same true cardinality cluster tightly around it, though any single estimate can land further off, especially for small cardinalities (m on the order of n or less) where linear-counting correction dominates and variance is higher. The test suite uses a generous 10% relative-error tolerance (an order of magnitude looser than the ~0.81% theoretical RSE at p = 14) against ground truth computed by a naive exact reference (List.exists-based deduplication), to stay robust without being flaky.

Two structural properties hold exactly, not just approximately: adding the same item any number of times never changes the estimate past the first addition (registers only ever increase, and the same string always hashes to the same register/value), and merge (a, a) always equals a's own estimate (register-wise max of identical registers is the identity).

Hashing

Hashing composes two steps: 64-bit FNV-1a, then a MurmurHash3-style fmix64 avalanche finalizer. The finalizer is not optional decoration — during development, using raw FNV-1a's top 14 bits as the register index for 1000 short sequential-integer strings ("0" .. "999") produced only about 90 distinct registers (instead of the ~970 the birthday paradox predicts for 1000 balls in 16384 bins), collapsing the estimate to a small fraction of the truth. FNV-1a mixes bits gradually via repeated XOR/multiply, so short inputs don't sufficiently perturb its high bits. fmix64 fixes this: every output bit depends on every input bit.

Build & test

Requires MLton and/or Poly/ML.

make test        # build + run the suite under MLton
make test-poly   # run the suite under Poly/ML
make all-tests   # both + byte-identical diff of stdout
make example     # build + run the demo
make clean

Installing with smlpkg

smlpkg add github.com/sjqtentacles/sml-hyperloglog
smlpkg sync

Reference lib/github.com/sjqtentacles/sml-hyperloglog/hyperloglog.mlb from your own .mlb (MLton / MLKit), or feed sources.mlb to tools/polybuild (Poly/ML).

Layout

sml.pkg                                            smlpkg manifest
Makefile                                           MLton + Poly/ML targets
.github/workflows/ci.yml                           CI: MLton + Poly/ML
lib/github.com/sjqtentacles/sml-hyperloglog/
  hyperloglog.sig    HYPERLOGLOG signature
  hyperloglog.sml     sketch implementation (FNV-1a + fmix64, registers, estimate)
  sources.mlb         ordered source list
  hyperloglog.mlb      public basis
examples/
  demo.sml            cardinality + merge walkthrough
test/
  harness.sml         shared assertion harness
  test.sml            structural + statistical-accuracy checks (18 checks)
  entry.sml / main.sml
tools/polybuild        Poly/ML build wrapper

Tests

18 checks: structural/exact (empty sketch estimates 0, precision bounds [4,16] raise outside range, repeated adds of the same item are exact no-ops, merge requires matching precision, merge (a, a) and merge (a, empty) reproduce a's own estimate exactly) plus statistical accuracy against a naive exact reference (List.exists-based deduplication) at N = 1000 and N = 5000 distinct items, and merge cardinality for both disjoint and overlapping sets, all within a 10% relative-error tolerance. Run make all-tests to verify identical output under both compilers.

License

MIT. See LICENSE.