Weighted Minwise Hashing Beats Linear Sketching for Inner Product Estimation
Summary: Weighted MinHash-based compact sketches for independent pairwise inner-product estimation, provably matching linear sketches on dense vectors and improving error bounds for sparse vectors with limited support overlap. Empirically outperforms CountSketch/JL and unweighted hashing, making it attractive for dataset-search and column-wise covariance/conditional-mean estimation. (summarized by gpt-5-mini on Feb 09 2026)
Incoming Non-self Citations Over Time
No non-self incoming citations found for this paper in this database.
Authors
- 1. Aline Bessa
- 2. Majid Daliri
- 3. Juliana Freire
- 4. Cameron Musco
- 5. Christopher Musco
- 6. Aécio Santos
- 7. Haoxiang Zhang
Incoming Citations (Sorted by Pagerank)
Showing 1 of 1 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 11,025 | Sampling Methods for Inner Product Sketching | 2024 | VLDB | 4.1945683e-05 |
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 8 of 8 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 34 | Similarity Search in High Dimensions via Hashing | 1999 | VLDB | 0.00076637636 |
| 383 | An Optimal Algorithm for the Distinct Elements Problem | 2010 | PODS | 0.00024820873 |
| 549 | Tracking Join and Self-Join Sizes in Limited Storage | 1999 | PODS | 0.00020376603 |
| 727 | On Synopses for Distinct-Value Estimation Under Multiset Operations | 2007 | SIGMOD | 0.00017508726 |
| 1,187 | JOSIE: Overlap Set Similarity Search for Finding Joinable Tables in Data Lakes | 2019 | SIGMOD | 0.00013443639 |
| 2,141 | LSH Ensemble: Internet-Scale Domain Search | 2016 | VLDB | 9.4542625e-05 |
| 3,708 | Is Min-Wise Hashing Optimal for Summarizing Set Intersection? | 2014 | PODS | 6.8247903e-05 |
| 3,824 | Correlation Sketches for Approximate Join-Correlation Queries | 2021 | SIGMOD | 6.7260705e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 8,599 | Bias-Aware Sketches | 2017 | VLDB | 4.4879268e-05 |
| 2,779 | Hashed Samples: Selectivity Estimators For Set Similarity Selection Queries | 2008 | VLDB | 8.1320575e-05 |
| 6,085 | Active Sampling Count Sketch (ASCS) for Online Sparse Estimation of a Trillion Scale Covariance Matrix | 2021 | SIGMOD | 5.2195267e-05 |
| 5,200 | SetSketch: Filling the Gap between MinHash and HyperLogLog | 2021 | VLDB | 5.6337581e-05 |
| 3,319 | Sketching Linear Classifiers over Data Streams | 2018 | SIGMOD | 7.226439e-05 |
| 8,635 | Bidirectionally Densifying LSH Sketches with Empty Bins | 2021 | SIGMOD | 4.4801584e-05 |
| 9,060 | Sketching via Hashing: From Heavy Hitters to Compressive Sensing to Sparse Fourier Transform | 2013 | PODS | 4.4039656e-05 |
| 3,708 | Is Min-Wise Hashing Optimal for Summarizing Set Intersection? | 2014 | PODS | 6.8247903e-05 |
| 9,082 | JoinSketch: A Sketch Algorithm for Accurate and Unbiased Inner-Product Estimation | 2023 | SIGMOD | 4.3998984e-05 |
| 11,025 | Sampling Methods for Inner Product Sketching | 2024 | VLDB | 4.1945683e-05 |