On the Complexity of Inner Product Similarity Join
Summary: Characterizes complexity of inner-product similarity join: proves SETH-based subquadratic approximation hardness and provides new upper and lower bounds for (A)LSH across signed/unsigned variants. Introduces a relaxed LSH avoiding asymmetry, novel asymmetric embeddings, and a linear-sketch indexing method that nearly matches the hardness limits. (summarized by gpt-5-mini on Feb 09 2026)
Incoming Non-self Citations Over Time
Authors
- 1. Thomas D. Ahle
- 2. Rasmus Pagh
- 3. Ilya Razenshteyn
- 4. Francesco Silvestri
Incoming Citations (Sorted by Pagerank)
Showing 4 of 4 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 3,780 | FEXIPRO: Fast and Exact Inner Product Retrieval in Recommender Systems | 2017 | SIGMOD | 6.7703467e-05 |
| 4,350 | Overlap Set Similarity Joins with Theoretical Guarantees | 2018 | SIGMOD | 6.2576191e-05 |
| 5,690 | FARGO: Fast Maximum Inner Product Search via Global Multi-Probing | 2023 | VLDB | 5.3699421e-05 |
| 7,636 | Allign: Aligning All-Pair Near-Duplicate Passages in Long Texts | 2021 | SIGMOD | 4.6863871e-05 |
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 9 of 9 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 |
| 78 | A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces | 1998 | VLDB | 0.00056385781 |
| 264 | Efficient Exact Set-Similarity Joins | 2006 | VLDB | 0.00029950264 |
| 1,299 | Bayesian Locality Sensitive Hashing for Fast Similarity Search | 2012 | VLDB | 0.00012712766 |
| 1,396 | Can We Beat the Prefix Filtering? An Adaptive Framework for Similarity Join and Search | 2012 | SIGMOD | 0.00012215253 |
| 2,588 | Pass-Join: A Partition-based Method for Similarity Joins | 2012 | VLDB | 8.4872437e-05 |
| 4,396 | LEMP: Fast Retrieval of Large Entries in a Matrix Product | 2015 | SIGMOD | 6.215279e-05 |
| 5,152 | String Similarity Measures and Joins with Synonyms | 2013 | SIGMOD | 5.6550754e-05 |
| 5,646 | GORDER: An Efficient Method for KNN Join Processing | 2004 | VLDB | 5.3924438e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 34 | Similarity Search in High Dimensions via Hashing | 1999 | VLDB | 0.00076824554 |
| 11,249 | A Two-Level Signature Scheme for Stable Set Similarity Joins | 2023 | VLDB | 4.1905499e-05 |
| 7,106 | Efficient Similarity Join and Search on Multi-Attribute Data | 2015 | SIGMOD | 4.8250163e-05 |
| 4,350 | Overlap Set Similarity Joins with Theoretical Guarantees | 2018 | SIGMOD | 6.2576191e-05 |
| 3,831 | Output-optimal Parallel Algorithms for Similarity Joins | 2017 | PODS | 6.7146681e-05 |
| 3,461 | Leveraging Set Relations in Exact Set Similarity Join | 2017 | VLDB | 7.0696567e-05 |
| 8,759 | Smooth Tradeoffs between Insert and Query Complexity in Nearest Neighbor Search | 2015 | PODS | 4.4520434e-05 |
| 248 | Efficient set joins on similarity predicates | 2004 | SIGMOD | 0.00030888982 |
| 5,222 | Similarity Join Size Estimation using Locality Sensitive Hashing | 2011 | VLDB | 5.6180462e-05 |
| 8,899 | Fast Approximate Similarity Join in Vector Databases | 2025 | SIGMOD | 4.4229886e-05 |