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,666 | Efficient framework for operating on data sketches | 2023 | VLDB | 5.3884066e-05 |
| 9,188 | OmniSketch: Efficient Multi-Dimensional High-Velocity Stream Analytics with Arbitrary Predicates | 2024 | VLDB | 5.3058708e-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 |
|---|---|---|---|---|
| 287 | Multi-Probe LSH: Efficient Indexing for High-Dimensional Similarity Search | 2007 | VLDB | 0.00022323585 |
| 432 | Mining Database Structure; Or, How to Build a Data Quality Browser | 2002 | SIGMOD | 0.00018572055 |
| 1,495 | LSH Ensemble: Internet-Scale Domain Search | 2016 | VLDB | 0.00010571481 |
| 2,792 | All-Distances Sketches, Revisited: HIP Estimators for Massive Graphs Analysis | 2014 | PODS | 8.1191853e-05 |
| 3,215 | Every Row Counts: Combining Sketches and Sampling for Accurate Group-By Result Estimates | 2019 | CIDR | 7.6324234e-05 |
| 5,257 | Efficient Estimation of Inclusion Coefficient using HyperLogLog Sketches | 2018 | VLDB | 6.2971456e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 6,934 | Better Cardinality Estimators for HyperLogLog, PCSA, and Beyond | 2023 | PODS |
| 2 | 5,257 | Efficient Estimation of Inclusion Coefficient using HyperLogLog Sketches | 2018 | VLDB |
| 3 | 4,260 | Set Similarity Joins on MapReduce: An Experimental Survey | 2018 | VLDB |
| 4 | 8,612 | Building Fast and Compact Sketches for Approximately Multi-Set Multi-Membership Querying | 2021 | SIGMOD |
| 5 | 11,164 | An LDP Compatible Sketch for Securely Approximating Set Intersection Cardinalities | 2024 | SIGMOD |
| 6 | 11,374 | Weighted Minwise Hashing Beats Linear Sketching for Inner Product Estimation | 2023 | PODS |
| 7 | 8,667 | On the algebra of data sketches | 2021 | VLDB |
| 8 | 5,998 | Approximate Distinct Counts for Billions of Datasets | 2019 | SIGMOD |
| 9 | 9,027 | JoinSketch: A Sketch Algorithm for Accurate and Unbiased Inner-Product Estimation | 2023 | SIGMOD |
| 10 | 12,550 | The Power of Two Min-Hashes for Similarity Search among Hierarchical Data Objects | 2008 | PODS |