Better Cardinality Estimators for HyperLogLog, PCSA, and Beyond
Summary: Introduce tau-Generalized-Remaining-Area (tau-GRA) estimators and a simpler unified analysis that casts prior estimators as integer‑tau cases. Fractional tau yields improved HyperLogLog/PCSA estimators near Cramér‑Rao variance and better Curtain‑sketch tradeoffs. (summarized by gpt-5-mini on Feb 09 2026)
Incoming Non-self Citations Over Time
Authors
- 1. Dingyu Wang (University of Michigan)
- 2. Seth Pettie (University of Michigan)
BibTeX Citation
@inproceedings{wang_pods23,
address = {New York, NY, USA},
series = {{PODS} '23},
title = {{Better Cardinality Estimators for HyperLogLog, PCSA, and Beyond}},
url = {https://dl.acm.org/doi/10.1145/3584372.3588680},
doi = {10.1145/3584372.3588680},
booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
publisher = {Association for Computing Machinery},
author = {Wang, Dingyu and Pettie, Seth},
year = {2023}
}
Incoming Citations (Sorted by Pagerank)
Showing 2 of 2 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 6,920 | UltraLogLog: A Practical and More Space-Efficient Alternative to HyperLogLog for Approximate Distinct Counting | 2024 | VLDB | 5.7390922e-05 |
| 10,310 | A Fast, Mergeable, and LDP Compatible Sketch for Counting the Number of Distinct Values in Fully Dynamic Tables | 2026 | SIGMOD | 5.093636e-05 |
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 2 of 2 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 482 | An Optimal Algorithm for the Distinct Elements Problem | 2010 | PODS | 0.00017772185 |
| 2,792 | All-Distances Sketches, Revisited: HIP Estimators for Massive Graphs Analysis | 2014 | PODS | 8.1191853e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 10,759 | Efficient and Accurate Differentially Private Cardinality Continual Releases | 2025 | SIGMOD |
| 2 | 11,503 | Bayesian Sketches for Volume Estimation in Data Streams | 2023 | VLDB |
| 3 | 8,666 | Efficient framework for operating on data sketches | 2023 | VLDB |
| 4 | 5,257 | Efficient Estimation of Inclusion Coefficient using HyperLogLog Sketches | 2018 | VLDB |
| 5 | 1,516 | Cardinality Estimation: An Experimental Survey | 2018 | VLDB |
| 6 | 5,864 | SetSketch: Filling the Gap between MinHash and HyperLogLog | 2021 | VLDB |
| 7 | 7,747 | Convolution and Cross-Correlation of Count Sketches Enables Fast Cardinality Estimation of Multi-Join Queries | 2024 | SIGMOD |
| 8 | 11,164 | An LDP Compatible Sketch for Securely Approximating Set Intersection Cardinalities | 2024 | SIGMOD |
| 9 | 12,669 | A Simple and Efficient Estimation Method for Stream Expression Cardinalities | 2007 | VLDB |
| 10 | 5,998 | Approximate Distinct Counts for Billions of Datasets | 2019 | SIGMOD |