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: 1645
Venue: PODS
Year: 2015
Pagerank: 6.1285141e-05
Overall Rank: 5,666 | 61.13%
DOI: 10.1145/2745754.2745761

Incoming Non-self Citations Over Time

Authors

1. Michael Kapralov (IBM)

BibTeX Citation

@inproceedings{kapralov_pods15,
        address = {New York, NY, USA},
        series = {{PODS} '15},
        title = {{Smooth Tradeoffs between Insert and Query Complexity in Nearest Neighbor Search}},
        url = {https://dl.acm.org/doi/10.1145/2745754.2745761},
        doi = {10.1145/2745754.2745761},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Kapralov, Michael},
        year = {2015}
}

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
6,583	Distance-Sensitive Hashing	2018	PODS	5.8359922e-05
9,317	Set Similarity Search for Skewed Data	2018	PODS	5.289545e-05
10,645	On the Adversarial Robustness of Locality-Sensitive Hashing in Hamming Space	2025	PODS	5.093636e-05
11,751	On the I/O Complexity of the k-Nearest Neighbors Problem	2020	PODS	5.093636e-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.0020210012
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
277	The SR-tree: An Index Structure for High-Dimensional Nearest Neighbor Queries	1997	SIGMOD	0.00022537944
287	Multi-Probe LSH: Efficient Indexing for High-Dimensional Similarity Search	2007	VLDB	0.00022323585

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,858	A General and Efficient Querying Method for Learning to Hash	2018	SIGMOD
2	990	SK-LSH: An Efficient Index Structure for Approximate Nearest Neighbor Search	2014	VLDB
3	580	SRS: Solving c-Approximate Nearest Neighbor Queries in High Dimensional Euclidean Space with a Tiny Index	2015	VLDB
4	3,389	Intelligent Probing for Locality Sensitive Hashing: Multi-Probe LSH and Beyond	2017	VLDB
5	2,673	DSH: Data Sensitive Hashing for High-Dimensional k-NN Search	2014	SIGMOD
6	332	Query-Aware Locality-Sensitive Hashing for Approximate Nearest Neighbor Search	2016	VLDB
7	21	Similarity Search in High Dimensions via Hashing	1999	VLDB
8	1,934	Towards Efficient Index Construction and Approximate Nearest Neighbor Search in High-Dimensional Spaces	2023	VLDB
9	581	Quality and Efficiency in High Dimensional Nearest Neighbor Search	2009	SIGMOD
10	287	Multi-Probe LSH: Efficient Indexing for High-Dimensional Similarity Search	2007	VLDB