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)

Paper ID: h99e1d75e207b423d
Venue: PODS
Year: 2016
Pagerank: 7.0089846e-05
Overall Rank: 3,809 | 74.40%
DOI: 10.1145/2902251.2902285

Incoming Non-self Citations Over Time

Authors

1. Thomas D. Ahle (IT University of Copenhagen)
2. Rasmus Pagh (IT University of Copenhagen)
3. Ilya Razenshteyn (Massachusetts Institute of Technology)
4. Francesco Silvestri (IT University of Copenhagen)

BibTeX Citation

@inproceedings{ahle_pods16,
        address = {New York, NY, USA},
        series = {{PODS} '16},
        title = {{On the Complexity of Inner Product Similarity Join}},
        url = {https://dl.acm.org/doi/10.1145/2902251.2902285},
        doi = {10.1145/2902251.2902285},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Ahle, Thomas D. and Pagh, Rasmus and Razenshteyn, Ilya and Silvestri, Francesco},
        year = {2016}
}

Incoming Citations (Sorted by Pagerank)

Showing 8 of 8 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,503	FEXIPRO: Fast and Exact Inner Product Retrieval in Recommender Systems	2017	SIGMOD	8.3786151e-05
3,596	Overlap Set Similarity Joins with Theoretical Guarantees	2018	SIGMOD	7.1790375e-05
5,268	FARGO: Fast Maximum Inner Product Search via Global Multi-Probing	2023	VLDB	6.2015316e-05
6,704	Distance-Sensitive Hashing	2018	PODS	5.7051402e-05
7,833	Allign: Aligning All-Pair Near-Duplicate Passages in Long Texts	2021	SIGMOD	5.443666e-05
9,495	Set Similarity Search for Skewed Data	2018	PODS	5.1708619e-05
10,449	Enhancing Graph-based Approximate Maximum Inner Product Search via Norm-Adaptive Partitioning	2026	SIGMOD	4.9793485e-05
12,194	Distributed Statistical Estimation of Matrix Products with Applications	2018	PODS	4.9793485e-05

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
20	Similarity Search in High Dimensions via Hashing	1999	VLDB	0.00057568153
45	A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces	1998	VLDB	0.0004503446
168	Efficient Exact Set-Similarity Joins	2006	VLDB	0.00027163517
963	Can We Beat the Prefix Filtering? An Adaptive Framework for Similarity Join and Search	2012	SIGMOD	0.00012816649
992	Bayesian Locality Sensitive Hashing for Fast Similarity Search	2012	VLDB	0.00012646771
1,933	Pass-Join: A Partition-based Method for Similarity Joins	2012	VLDB	9.3459285e-05
3,611	LEMP: Fast Retrieval of Large Entries in a Matrix Product	2015	SIGMOD	7.1628753e-05
5,207	String Similarity Measures and Joins with Synonyms	2013	SIGMOD	6.2272365e-05
5,532	GORDER: An Efficient Method for KNN Join Processing	2004	VLDB	6.0932822e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	20	Similarity Search in High Dimensions via Hashing	1999	VLDB
2	11,759	A Two-Level Signature Scheme for Stable Set Similarity Joins	2023	VLDB
3	7,030	Efficient Similarity Join and Search on Multi-Attribute Data	2015	SIGMOD
4	3,596	Overlap Set Similarity Joins with Theoretical Guarantees	2018	SIGMOD
5	2,464	Output-optimal Parallel Algorithms for Similarity Joins	2017	PODS
6	2,921	Leveraging Set Relations in Exact Set Similarity Join	2017	VLDB
7	5,796	Smooth Tradeoffs between Insert and Query Complexity in Nearest Neighbor Search	2015	PODS
8	201	Efficient set joins on similarity predicates	2004	SIGMOD
9	4,958	Similarity Join Size Estimation using Locality Sensitive Hashing	2011	VLDB
10	8,408	Fast Approximate Similarity Join in Vector Databases	2025	SIGMOD