SetSketch: Filling the Gap between MinHash and HyperLogLog
Summary: SetSketch bridges MinHash and HyperLogLog with a commutative, idempotent insert and mergeable state for distributed sketches. It delivers fast, robust estimators for cardinality and joint quantities, enables similarity search, and its joint estimator often outperforms state-of-the-art on related structures. (summarized by gpt-5-nano on Feb 09 2026)
Incoming Non-self Citations Over Time
Authors
- 1. Otmar Ertl (Dynatrace Research)
BibTeX Citation
@article{ertl_vldb21,
title = {{SetSketch: Filling the Gap between MinHash and HyperLogLog}},
author = {Ertl, Otmar},
journal = {PVLDB},
series = {{VLDB} '21},
volume = {14},
number = {11},
pages = {2244--2257},
doi = {10.14778/3476249.3476276},
url = {https://doi.org/10.14778/3476249.3476276},
year = {2021}
}Incoming Citations (Sorted by Pagerank)
Showing 2 of 2 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 8,835 | Efficient framework for operating on data sketches | 2023 | VLDB | 5.2675052e-05 |
| 9,367 | OmniSketch: Efficient Multi-Dimensional High-Velocity Stream Analytics with Arbitrary Predicates | 2024 | VLDB | 5.1868213e-05 |
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 6 of 6 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 280 | Multi-Probe LSH: Efficient Indexing for High-Dimensional Similarity Search | 2007 | VLDB | 0.0002230467 |
| 435 | Mining Database Structure; Or, How to Build a Data Quality Browser | 2002 | SIGMOD | 0.0001832766 |
| 1,318 | LSH Ensemble: Internet-Scale Domain Search | 2016 | VLDB | 0.00011047393 |
| 2,852 | All-Distances Sketches, Revisited: HIP Estimators for Massive Graphs Analysis | 2014 | PODS | 7.9412916e-05 |
| 3,131 | Every Row Counts: Combining Sketches and Sampling for Accurate Group-By Result Estimates | 2019 | CIDR | 7.6141006e-05 |
| 5,108 | Efficient Estimation of Inclusion Coefficient using HyperLogLog Sketches | 2018 | VLDB | 6.2696201e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 5,108 | Efficient Estimation of Inclusion Coefficient using HyperLogLog Sketches | 2018 | VLDB |
| 2 | 7,074 | Better Cardinality Estimators for HyperLogLog, PCSA, and Beyond | 2023 | PODS |
| 3 | 4,274 | Set Similarity Joins on MapReduce: An Experimental Survey | 2018 | VLDB |
| 4 | 7,184 | Building Fast and Compact Sketches for Approximately Multi-Set Multi-Membership Querying | 2021 | SIGMOD |
| 5 | 11,510 | An LDP Compatible Sketch for Securely Approximating Set Intersection Cardinalities | 2024 | SIGMOD |
| 6 | 11,690 | Weighted Minwise Hashing Beats Linear Sketching for Inner Product Estimation | 2023 | PODS |
| 7 | 8,836 | On the algebra of data sketches | 2021 | VLDB |
| 8 | 8,035 | JoinSketch: A Sketch Algorithm for Accurate and Unbiased Inner-Product Estimation | 2023 | SIGMOD |
| 9 | 6,122 | Approximate Distinct Counts for Billions of Datasets | 2019 | SIGMOD |
| 10 | 12,840 | The Power of Two Min-Hashes for Similarity Search among Hierarchical Data Objects | 2008 | PODS |