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

Mayank Goswami, Riko Jacob, Rasmus Pagh

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 indivisibili…