FA-73245 / Probabilistic sketches / Member archive

K-minimum-values distinct counting: estimator uses k instead of k-1 · case 05

Distinct counts are biased upward by a factor k/(k-1).

Member previewVariant 5 · 3 implementations · 8 checks per implementation

Case contract

Input {k, a, b} lists of 32-bit hashes. Each sketch keeps the k smallest distinct hashes. With fewer than k kept values the count is exact (their number); otherwise the estimate is round((k-1) * 2^32 / v_k) with v_k the k-th smallest. The union sketch is the k smallest distinct values of both kept sets. The intersection is exact when the union has fewer than k values, else round(c/k * union estimate) where c counts union-sketch values kept by both inputs. Return [estA, estB, estUnion, estIntersection].

Why this case matters

KMV sketches power approximate COUNT(DISTINCT) with set operations in analytics engines; the unbiased (k-1)/v_k form and the union rule are easy to get subtly wrong.

One recorded failure

Sample boundary fixture

This sample comes from the broken implementation of a controlled reproducer.

Boundary fixture	Actual	Expected	Outcome
streams 0 k=4	`[8, 8, 13, 3]`	`[6, 6, 10, 2]`	Failed

MEMBER ARCHIVE

The complete case is available to members.

This record includes three runnable implementations, regression fixtures, execution results, and source hashes.

Member access is invitation-based. Sign in with your invited account to inspect the sources.