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,028 | Sampling Methods for Inner Product Sketching | 2024 | VLDB | 4.1905499e-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.00076824554 |
| 449 | An Optimal Algorithm for the Distinct Elements Problem | 2010 | PODS | 0.00022914472 |
| 550 | Tracking Join and Self-Join Sizes in Limited Storage | 1999 | PODS | 0.00020346247 |
| 737 | On Synopses for Distinct-Value Estimation Under Multiset Operations | 2007 | SIGMOD | 0.00017377393 |
| 1,185 | JOSIE: Overlap Set Similarity Search for Finding Joinable Tables in Data Lakes | 2019 | SIGMOD | 0.00013432692 |
| 2,142 | LSH Ensemble: Internet-Scale Domain Search | 2016 | VLDB | 9.4461701e-05 |
| 3,713 | Is Min-Wise Hashing Optimal for Summarizing Set Intersection? | 2014 | PODS | 6.8182579e-05 |
| 3,827 | Correlation Sketches for Approximate Join-Correlation Queries | 2021 | SIGMOD | 6.7195959e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 8,586 | Bias-Aware Sketches | 2017 | VLDB | 4.4855966e-05 |
| 2,779 | Hashed Samples: Selectivity Estimators For Set Similarity Selection Queries | 2008 | VLDB | 8.1314377e-05 |
| 6,089 | Active Sampling Count Sketch (ASCS) for Online Sparse Estimation of a Trillion Scale Covariance Matrix | 2021 | SIGMOD | 5.2145151e-05 |
| 5,201 | SetSketch: Filling the Gap between MinHash and HyperLogLog | 2021 | VLDB | 5.6283451e-05 |
| 3,322 | Sketching Linear Classifiers over Data Streams | 2018 | SIGMOD | 7.217965e-05 |
| 8,635 | Bidirectionally Densifying LSH Sketches with Empty Bins | 2021 | SIGMOD | 4.4758632e-05 |
| 8,932 | Sketching via Hashing: From Heavy Hitters to Compressive Sensing to Sparse Fourier Transform | 2013 | PODS | 4.4229886e-05 |
| 3,713 | Is Min-Wise Hashing Optimal for Summarizing Set Intersection? | 2014 | PODS | 6.8182579e-05 |
| 9,079 | JoinSketch: A Sketch Algorithm for Accurate and Unbiased Inner-Product Estimation | 2023 | SIGMOD | 4.3956812e-05 |
| 11,028 | Sampling Methods for Inner Product Sketching | 2024 | VLDB | 4.1905499e-05 |