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 |
|---|---|---|---|---|
| 7,061 | UltraLogLog: A Practical and More Space-Efficient Alternative to HyperLogLog for Approximate Distinct Counting | 2024 | VLDB | 5.6103223e-05 |
| 10,521 | A Fast, Mergeable, and LDP Compatible Sketch for Counting the Number of Distinct Values in Fully Dynamic Tables | 2026 | SIGMOD | 4.9793485e-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 |
|---|---|---|---|---|
| 494 | An Optimal Algorithm for the Distinct Elements Problem | 2010 | PODS | 0.00017387321 |
| 2,852 | All-Distances Sketches, Revisited: HIP Estimators for Massive Graphs Analysis | 2014 | PODS | 7.9412916e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 11,183 | Efficient and Accurate Differentially Private Cardinality Continual Releases | 2025 | SIGMOD |
| 2 | 11,812 | Bayesian Sketches for Volume Estimation in Data Streams | 2023 | VLDB |
| 3 | 8,835 | Efficient framework for operating on data sketches | 2023 | VLDB |
| 4 | 5,108 | Efficient Estimation of Inclusion Coefficient using HyperLogLog Sketches | 2018 | VLDB |
| 5 | 1,536 | Cardinality Estimation: An Experimental Survey | 2018 | VLDB |
| 6 | 5,987 | SetSketch: Filling the Gap between MinHash and HyperLogLog | 2021 | VLDB |
| 7 | 7,566 | Convolution and Cross-Correlation of Count Sketches Enables Fast Cardinality Estimation of Multi-Join Queries | 2024 | SIGMOD |
| 8 | 11,510 | An LDP Compatible Sketch for Securely Approximating Set Intersection Cardinalities | 2024 | SIGMOD |
| 9 | 12,959 | A Simple and Efficient Estimation Method for Stream Expression Cardinalities | 2007 | VLDB |
| 10 | 6,122 | Approximate Distinct Counts for Billions of Datasets | 2019 | SIGMOD |