Smooth Tradeoffs between Insert and Query Complexity in Nearest Neighbor Search

Summary: L2 similarity-search scheme providing a smooth, tunable tradeoff between insert complexity A and query complexity B, interpolating between classical LSH and Entropy LSH regimes. Data-oblivious construction and analysis match or improve prior bounds up to lower-order exponent terms. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1646
Venue: PODS
Year: 2015
Pagerank: 4.456315e-05
Overall Rank: 8,763 | 39.04%
DOI: 10.1145/2745754.2745761

Incoming Non-self Citations Over Time

Authors

1. Michael Kapralov

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,351	On the Adversarial Robustness of Locality-Sensitive Hashing in Hamming Space	2025	PODS	4.1945683e-05
11,554	On the I/O Complexity of the k-Nearest Neighbors Problem	2020	PODS	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 5 of 5 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
2	R-Trees: A Dynamic Index Structure For Spatial Searching	1984	SIGMOD	0.0032169493
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
284	The SR-tree: An Index Structure for High-Dimensional Nearest Neighbor Queries	1997	SIGMOD	0.00028994728
400	Multi-Probe LSH: Efficient Indexing for High-Dimensional Similarity Search	2007	VLDB	0.0002427237

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
4,609	A General and Efficient Querying Method for Learning to Hash	2018	SIGMOD	6.0528541e-05
867	SRS: Solving c-Approximate Nearest Neighbor Queries in High Dimensional Euclidean Space with a Tiny Index	2015	VLDB	0.00015792021
1,229	SK-LSH : An Efficient Index Structure for Approximate Nearest Neighbor Search	2014	VLDB	0.00013157271
3,056	DSH: Data Sensitive Hashing for High-Dimensional k-NN Search	2014	SIGMOD	7.6432146e-05
3,938	Intelligent Probing for Locality Sensitive Hashing: Multi-Probe LSH and Beyond	2017	VLDB	6.6155909e-05
562	Query-Aware Locality-Sensitive Hashing for Approximate Nearest Neighbor Search	2016	VLDB	0.00020091752
34	Similarity Search in High Dimensions via Hashing	1999	VLDB	0.00076637636
2,971	Towards Efficient Index Construction and Approximate Nearest Neighbor Search in High-Dimensional Spaces	2023	VLDB	7.7970531e-05
682	Quality and Efficiency in High Dimensional Nearest Neighbor Search	2009	SIGMOD	0.00018201541
400	Multi-Probe LSH: Efficient Indexing for High-Dimensional Similarity Search	2007	VLDB	0.0002427237