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,844 | Efficient framework for operating on data sketches | 2023 | VLDB | 5.2650116e-05 |
| 9,376 | OmniSketch: Efficient Multi-Dimensional High-Velocity Stream Analytics with Arbitrary Predicates | 2024 | VLDB | 5.1843659e-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 |
|---|---|---|---|---|
| 278 | Multi-Probe LSH: Efficient Indexing for High-Dimensional Similarity Search | 2007 | VLDB | 0.00022310642 |
| 435 | Mining Database Structure; Or, How to Build a Data Quality Browser | 2002 | SIGMOD | 0.0001831946 |
| 1,319 | LSH Ensemble: Internet-Scale Domain Search | 2016 | VLDB | 0.00011042864 |
| 2,852 | All-Distances Sketches, Revisited: HIP Estimators for Massive Graphs Analysis | 2014 | PODS | 7.9377182e-05 |
| 3,132 | Every Row Counts: Combining Sketches and Sampling for Accurate Group-By Result Estimates | 2019 | CIDR | 7.6107287e-05 |
| 5,112 | Efficient Estimation of Inclusion Coefficient using HyperLogLog Sketches | 2018 | VLDB | 6.2668086e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 5,112 | Efficient Estimation of Inclusion Coefficient using HyperLogLog Sketches | 2018 | VLDB |
| 2 | 7,076 | Better Cardinality Estimators for HyperLogLog, PCSA, and Beyond | 2023 | PODS |
| 3 | 4,275 | Set Similarity Joins on MapReduce: An Experimental Survey | 2018 | VLDB |
| 4 | 7,186 | Building Fast and Compact Sketches for Approximately Multi-Set Multi-Membership Querying | 2021 | SIGMOD |
| 5 | 11,516 | An LDP Compatible Sketch for Securely Approximating Set Intersection Cardinalities | 2024 | SIGMOD |
| 6 | 11,696 | Weighted Minwise Hashing Beats Linear Sketching for Inner Product Estimation | 2023 | PODS |
| 7 | 8,845 | On the algebra of data sketches | 2021 | VLDB |
| 8 | 8,042 | JoinSketch: A Sketch Algorithm for Accurate and Unbiased Inner-Product Estimation | 2023 | SIGMOD |
| 9 | 6,124 | Approximate Distinct Counts for Billions of Datasets | 2019 | SIGMOD |
| 10 | 12,846 | The Power of Two Min-Hashes for Similarity Search among Hierarchical Data Objects | 2008 | PODS |