On the I/O complexity of the k-nearest neighbor problem

Abstract

We consider static, external memory indexes for exact and approximate versions of the $k$-nearest neighbor ($k$-NN) problem, and show new lower bounds under a standard indivisibility assumption: - Polynomial space indexing schemes for high-dimensional $k$-NN in Hamming space cannot take advantage of block transfers: $\Omega (k)$ block reads are needed to to answer a query. - For the ${\ell }_{\infty }$ metric the lower bound holds even if we allow $c$-appoximate nearest neighbors to be returned, for $c\in (1,3)$. - The restriction to $c<3$ is necessary: For every metric there exists an indexing scheme in the indexability model of Hellerstein et al.~using space $O(kn)$, where $n$ is the number of points, that can retrieve $k$ 3-approximate nearest neighbors using $\lceil k/B\rceil$ I/Os, which is optimal. - For specific metrics, data structures with better approximation factors are possible. For $k$-NN in Hamming space and every approximation factor $c>1$ there exists a polynomial space data structure that returns $k$ $c$-approximate nearest neighbors in $\lceil k/B\rceil$ I/Os. To show these lower bounds we develop two new techniques: First, to handle that approximation algorithms have more freedom in deciding which result set to return we develop a relaxed version of the $\lambda$-set workload technique of Hellerstein et al. This technique allows us to show lower bounds that hold in $d\ge n$ dimensions. To extend the lower bounds down to $d=O(k\log (n/k))$ dimensions, we develop a new deterministic dimension reduction technique that may be of independent interest.

Appears in proceedings of PODS 2020