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: 1679
Venue: PODS
Year: 2016
Pagerank: 7.108802e-05
Overall Rank: 3,806 | 73.89%
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,938	FEXIPRO: Fast and Exact Inner Product Retrieval in Recommender Systems	2017	SIGMOD	7.942728e-05
3,724	Overlap Set Similarity Joins with Theoretical Guarantees	2018	SIGMOD	7.1715735e-05
5,223	FARGO: Fast Maximum Inner Product Search via Global Multi-Probing	2023	VLDB	6.3102417e-05
6,583	Distance-Sensitive Hashing	2018	PODS	5.8359922e-05
7,676	Allign: Aligning All-Pair Near-Duplicate Passages in Long Texts	2021	SIGMOD	5.5686107e-05
9,317	Set Similarity Search for Skewed Data	2018	PODS	5.289545e-05
10,233	Enhancing Graph-based Approximate Maximum Inner Product Search via Norm-Adaptive Partitioning	2026	SIGMOD	5.093636e-05
11,894	Distributed Statistical Estimation of Matrix Products with Applications	2018	PODS	5.093636e-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
21	Similarity Search in High Dimensions via Hashing	1999	VLDB	0.00056760516
46	A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces	1998	VLDB	0.00044853085
169	Efficient Exact Set-Similarity Joins	2006	VLDB	0.0002743469
975	Can We Beat the Prefix Filtering? An Adaptive Framework for Similarity Join and Search	2012	SIGMOD	0.00012870645
991	Bayesian Locality Sensitive Hashing for Fast Similarity Search	2012	VLDB	0.00012793339
1,886	Pass-Join: A Partition-based Method for Similarity Joins	2012	VLDB	9.5358137e-05
3,676	LEMP: Fast Retrieval of Large Entries in a Matrix Product	2015	SIGMOD	7.2094091e-05
5,088	String Similarity Measures and Joins with Synonyms	2013	SIGMOD	6.3673276e-05
5,405	GORDER: An Efficient Method for KNN Join Processing	2004	VLDB	6.2291247e-05

Semantically Similar Papers

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