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.0102162e-05
Overall Rank: 3,774 | 74.71%
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,293	FEXIPRO: Fast and Exact Inner Product Retrieval in Recommender Systems	2017	SIGMOD	8.6780858e-05
3,604	Overlap Set Similarity Joins with Theoretical Guarantees	2018	SIGMOD	7.1548073e-05
5,294	FARGO: Fast Maximum Inner Product Search via Global Multi-Probing	2023	VLDB	6.1780995e-05
6,717	Distance-Sensitive Hashing	2018	PODS	5.6843145e-05
7,854	Allign: Aligning All-Pair Near-Duplicate Passages in Long Texts	2021	SIGMOD	5.4230974e-05
9,535	Set Similarity Search for Skewed Data	2018	PODS	5.151324e-05
10,526	Enhancing Graph-based Approximate Maximum Inner Product Search via Norm-Adaptive Partitioning	2026	SIGMOD	4.9605343e-05
12,243	Distributed Statistical Estimation of Matrix Products with Applications	2018	PODS	4.9605343e-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.00057610161
45	A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces	1998	VLDB	0.00044967652
169	Efficient Exact Set-Similarity Joins	2006	VLDB	0.00027077763
966	Can We Beat the Prefix Filtering? An Adaptive Framework for Similarity Join and Search	2012	SIGMOD	0.00012777679
987	Bayesian Locality Sensitive Hashing for Fast Similarity Search	2012	VLDB	0.00012643645
1,941	Pass-Join: A Partition-based Method for Similarity Joins	2012	VLDB	9.3141839e-05
3,254	LEMP: Fast Retrieval of Large Entries in a Matrix Product	2015	SIGMOD	7.4748207e-05
5,233	String Similarity Measures and Joins with Synonyms	2013	SIGMOD	6.2049921e-05
5,547	GORDER: An Efficient Method for KNN Join Processing	2004	VLDB	6.0715188e-05

Semantically Similar Papers

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