On the I/O Complexity of the k-Nearest Neighbors Problem

Summary: Shows Ω(k) I/O lower bounds for static external-memory k-NN under an indivisibility assumption: polynomial-space schemes need Ω(k) block reads in high‑dim Hamming, and for L_∞ the bound holds for 1<c<3. Introduces a relaxed λ-set workload and a deterministic dimension-reduction to extend bounds to d=O(k log(n/k)), and proves tightness at c=3 via an O(k n)-space index achieving ⌈k/B⌉ I/Os. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1812
Venue: PODS
Year: 2020
Pagerank: 5.093636e-05
Overall Rank: 11,751 | 19.38%
DOI: 10.1145/3375395.3387649

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Mayank Goswami (Queens College, City University of New York)
2. Riko Jacob (IT University of Copenhagen)
3. Rasmus Pagh (Basic Algorithms Research Copenhagen; IT University of Copenhagen)

BibTeX Citation

@inproceedings{goswami_pods20,
        address = {New York, NY, USA},
        series = {{PODS} '20},
        title = {{On the I/O Complexity of the k-Nearest Neighbors Problem}},
        url = {https://dl.acm.org/doi/10.1145/3375395.3387649},
        doi = {10.1145/3375395.3387649},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Goswami, Mayank and Jacob, Riko and Pagh, Rasmus},
        year = {2020}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 8 of 8 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
202	Generalized Search Trees for Database Systems (Extended Abstract)	1995	VLDB	0.00025454884
1,137	A Cost Model For Nearest Neighbor Search in High-Dimensional Data Space	1997	PODS	0.00012027131
1,512	On the Analysis of Indexing Schemes	1997	PODS	0.00010536001
2,443	Independent Range Sampling	2014	PODS	8.5754434e-05
2,462	Output-optimal Parallel Algorithms for Similarity Joins	2017	PODS	8.5487602e-05
5,666	Smooth Tradeoffs between Insert and Query Complexity in Nearest Neighbor Search	2015	PODS	6.1285141e-05
8,937	Dynamic Indexability and Lower Bounds for Dynamic One-Dimensional Range Query Indexes	2009	PODS	5.3483178e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,972	Tight bounds for 2-dimensional indexing schemes	1998	PODS
2	580	SRS: Solving c-Approximate Nearest Neighbor Queries in High Dimensional Euclidean Space with a Tiny Index	2015	VLDB
3	8,765	Contorting High Dimensional Data for Efficient Main Memory KNN Processing	2003	SIGMOD
4	1,137	A Cost Model For Nearest Neighbor Search in High-Dimensional Data Space	1997	PODS
5	7,259	Efficient Dynamic Indexing for Range Filtered Approximate Nearest Neighbor Search	2025	SIGMOD
6	705	HD-Index: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces	2018	VLDB
7	3,710	Efficient Reverse k-Nearest Neighbor Search in Arbitrary Metric Spaces	2006	SIGMOD
8	4,730	A Lower Bound Theorem for Indexing Schemes and its Application to Multidimensional Range Queries	1998	PODS
9	6,753	Optimal Indexing Using Near-Minimal Space [Extended Abstract]	2003	PODS
10	1,529	On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract)	1999	PODS