REVIEW 2 cited by
New cardinality estimation algorithms for HyperLogLog sketches
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
read the original abstract
This paper presents new methods to estimate the cardinalities of data sets recorded by HyperLogLog sketches. A theoretically motivated extension to the original estimator is presented that eliminates the bias for small and large cardinalities. Based on the maximum likelihood principle a second unbiased method is derived together with a robust and efficient numerical algorithm to calculate the estimate. The maximum likelihood approach can also be applied to more than a single HyperLogLog sketch. In particular, it is shown that it gives more precise cardinality estimates for union, intersection, or relative complements of two sets that are both represented by HyperLogLog sketches compared to the conventional technique using the inclusion-exclusion principle. All the new methods are demonstrated and verified by extensive simulations.
Forward citations
Cited by 2 Pith papers
-
HyperLogLog for probabilists
HyperLogLog's raw estimator satisfies P(m²Z_N ≤ μN) ≤ exp(−m(1/μ − 1 + log μ)) for every N ≥ 1, plus a right-tail bound with an explicit correction term.
-
Mergeable Model-Side Aggregation States for Long-Context Language Models
Fixed-budget HyperLogLog states maintained alongside a frozen LLM preserve set-based aggregation and improve long-context reasoning accuracy.
Discussion (0). Sign in to comment.