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: h6de2017645d18b6b
Venue: PODS
Year: 2020
Pagerank: 4.9605343e-05
Overall Rank: 12,104 | 18.87%
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
20	Similarity Search in High Dimensions via Hashing	1999	VLDB	0.00057610161
210	Generalized Search Trees for Database Systems (Extended Abstract)	1995	VLDB	0.00024910589
1,161	A Cost Model For Nearest Neighbor Search in High-Dimensional Data Space	1997	PODS	0.00011733128
1,527	On the Analysis of Indexing Schemes	1997	PODS	0.00010326893
2,475	Output-optimal Parallel Algorithms for Similarity Joins	2017	PODS	8.3947133e-05
2,504	Independent Range Sampling	2014	PODS	8.3571366e-05
5,814	Smooth Tradeoffs between Insert and Query Complexity in Nearest Neighbor Search	2015	PODS	5.9684385e-05
9,129	Dynamic Indexability and Lower Bounds for Dynamic One-Dimensional Range Query Indexes	2009	PODS	5.208561e-05

Semantically Similar Papers

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