Is Min-Wise Hashing Optimal for Summarizing Set Intersection?
Summary: Information-theoretic lower bounds show b-bit minwise hashing is space-optimal (variance within constant factor) for estimating intersections of two predicates, but k-permutation/min-hash schemes deteriorate as m grows. We provide new lower/upper bounds and a novel summary that nearly attains the lower bound for m≥2, asymptotically outperforming k-permutation schemes by Θ(m/log m) and subsampling by Θ(log n_max). (summarized by gpt-5-mini on Feb 09 2026)
Incoming Non-self Citations Over Time
Authors
- 1. Rasmus Pagh (IT University of Copenhagen)
- 2. Morten Stöckel (IT University of Copenhagen)
- 3. David P. Woodruff (IBM)
BibTeX Citation
@inproceedings{pagh_pods14,
address = {New York, NY, USA},
series = {{PODS} '14},
title = {{Is Min-Wise Hashing Optimal for Summarizing Set Intersection?}},
url = {https://dl.acm.org/doi/10.1145/2594538.2594554},
doi = {10.1145/2594538.2594554},
booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
publisher = {Association for Computing Machinery},
author = {Pagh, Rasmus and Stöckel, Morten and Woodruff, David P.},
year = {2014}
}Incoming Citations (Sorted by Pagerank)
Showing 7 of 7 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 5,257 | Efficient Estimation of Inclusion Coefficient using HyperLogLog Sketches | 2018 | VLDB | 6.2971456e-05 |
| 5,743 | Joins on Samples: A Theoretical Guide for Practitioners | 2020 | VLDB | 6.1025457e-05 |
| 7,328 | On the Feasibility of Forgetting in Data Streams | 2024 | PODS | 5.6435171e-05 |
| 7,433 | Selectivity Estimation on Streaming Spatio-Textual Data Using Local Correlations | 2015 | VLDB | 5.6197531e-05 |
| 8,252 | Sampling Methods for Inner Product Sketching | 2024 | VLDB | 5.4574671e-05 |
| 9,188 | OmniSketch: Efficient Multi-Dimensional High-Velocity Stream Analytics with Arbitrary Predicates | 2024 | VLDB | 5.3058708e-05 |
| 11,374 | Weighted Minwise Hashing Beats Linear Sketching for Inner Product Estimation | 2023 | PODS | 5.093636e-05 |
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 4 of 4 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 |
| 4,285 | Beyond Simple Aggregates: Indexing for Summary Queries | 2011 | PODS | 6.7812351e-05 |
| 5,995 | Coordinated Weighted Sampling for Estimating Aggregates Over Multiple Weight Assignments | 2009 | VLDB | 6.0155431e-05 |
| 6,677 | Information Complexity: a Tutorial | 2010 | PODS | 5.8056405e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 3,724 | Overlap Set Similarity Joins with Theoretical Guarantees | 2018 | SIGMOD |
| 2 | 4,857 | Similarity Join Size Estimation using Locality Sensitive Hashing | 2011 | VLDB |
| 3 | 2,245 | Fast Set Intersection in Memory | 2011 | VLDB |
| 4 | 6,818 | Space-efficient Substring Occurrence Estimation | 2011 | PODS |
| 5 | 2,061 | Selectivity Estimation For Boolean Queries | 2000 | PODS |
| 6 | 11,374 | Weighted Minwise Hashing Beats Linear Sketching for Inner Product Estimation | 2023 | PODS |
| 7 | 2,308 | Hashed Samples: Selectivity Estimators For Set Similarity Selection Queries | 2008 | VLDB |
| 8 | 5,998 | Approximate Distinct Counts for Billions of Datasets | 2019 | SIGMOD |
| 9 | 8,728 | Computing A Well-Representative Summary of Conjunctive Query Results | 2024 | PODS |
| 10 | 4,450 | Power-Law Based Estimation of Set Similarity Join Size | 2009 | VLDB |