FA-73040 / Probabilistic sketches / Member archive

HyperLogLog merge across precisions: merge adds registers · case 05

Merged ranks exceed any rank either stream could produce, massively overestimating the union.

Member previewVariant 5 · 3 implementations · 7 checks per implementation

Case contract

Input {a, b}, each {p, regs}. Both sketches are folded to q = min precision. Folding from p to q with d = p - q maps register j to j >> d; if the low d bits of j are non-zero they become the leading bits of the new remainder, giving rank d - bitlen(low) + 1, otherwise the rank is r + d. Empty registers contribute nothing. The merged sketch is the element-wise maximum. Return [q, regs].

Why this case matters

Merging distinct-count sketches produced with different precision settings requires re-deriving ranks, not just re-indexing registers.

One recorded failure

Sample boundary fixture

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

Boundary fixture	Actual	Expected	Outcome
fold p5 into p3	`[3, [7, 3, 4, 6, 7, 9, 7, 0]]`	`[3, [5, 2, 3, 4, 5, 6, 5, 0]]`	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.