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,772 | FEXIPRO: Fast and Exact Inner Product Retrieval in Recommender Systems | 2017 | SIGMOD | 6.7761705e-05 |
| 4,353 | Overlap Set Similarity Joins with Theoretical Guarantees | 2018 | SIGMOD | 6.263585e-05 |
| 5,707 | FARGO: Fast Maximum Inner Product Search via Global Multi-Probing | 2023 | VLDB | 5.3611041e-05 |
| 7,635 | Allign: Aligning All-Pair Near-Duplicate Passages in Long Texts | 2021 | SIGMOD | 4.6908858e-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.00076637636 |
| 79 | A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces | 1998 | VLDB | 0.00056242144 |
| 266 | Efficient Exact Set-Similarity Joins | 2006 | VLDB | 0.00029718727 |
| 1,305 | Bayesian Locality Sensitive Hashing for Fast Similarity Search | 2012 | VLDB | 0.00012687101 |
| 1,396 | Can We Beat the Prefix Filtering? An Adaptive Framework for Similarity Join and Search | 2012 | SIGMOD | 0.00012204748 |
| 2,592 | Pass-Join: A Partition-based Method for Similarity Joins | 2012 | VLDB | 8.4795761e-05 |
| 4,401 | LEMP: Fast Retrieval of Large Entries in a Matrix Product | 2015 | SIGMOD | 6.2211271e-05 |
| 5,151 | String Similarity Measures and Joins with Synonyms | 2013 | SIGMOD | 5.6609851e-05 |
| 5,636 | GORDER: An Efficient Method for KNN Join Processing | 2004 | VLDB | 5.3981191e-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.00076637636 |
| 11,247 | A Two-Level Signature Scheme for Stable Set Similarity Joins | 2023 | VLDB | 4.1945683e-05 |
| 7,109 | Efficient Similarity Join and Search on Multi-Attribute Data | 2015 | SIGMOD | 4.8292998e-05 |
| 4,353 | Overlap Set Similarity Joins with Theoretical Guarantees | 2018 | SIGMOD | 6.263585e-05 |
| 3,833 | Output-optimal Parallel Algorithms for Similarity Joins | 2017 | PODS | 6.7173578e-05 |
| 3,490 | Leveraging Set Relations in Exact Set Similarity Join | 2017 | VLDB | 7.0465856e-05 |
| 8,763 | Smooth Tradeoffs between Insert and Query Complexity in Nearest Neighbor Search | 2015 | PODS | 4.456315e-05 |
| 250 | Efficient set joins on similarity predicates | 2004 | SIGMOD | 0.00030661988 |
| 5,220 | Similarity Join Size Estimation using Locality Sensitive Hashing | 2011 | VLDB | 5.6216111e-05 |
| 8,899 | Fast Approximate Similarity Join in Vector Databases | 2025 | SIGMOD | 4.427232e-05 |