Efficient Reductions for k-Nearest Neighbor Search

Theory for high-dimensional nearest-neighbor search often assumes a known search radius, a specified approximation ratio, and a request for one nearby point. Practical applications instead ask for the exact k nearest points without knowing the relevant radius; an appropriate approximation parameter also depends on the data distribution. Existing reductions between these formulations introduce polylogarithmic time or space overhead that can make them unattractive in practice. This talk presents simple, more efficient reductions that solve k-nearest-neighbor search using locality-sensitive hashing and address this gap between theoretical guarantees and practical queries. Joint work with Tobias Christiani and Mikkel Thorup.