Revisiting kd-tree for Nearest Neighbor Search

TLDR

The k‑d tree has historically been considered ineffective for exact nearest‑neighbor search in high‑dimensional data, offering no significant advantage over brute‑force methods and being mainly used for approximate search without theoretical guarantees. This work aims to develop k‑d tree–based approximate nearest‑neighbor schemes that provide rigorous accuracy guarantees. The authors extend randomized‑partition trees to achieve O(d log d + log n) query time for n points in d dimensions. Empirical results confirm the accuracy and query‑time guarantees, showing markedly better scaling at the same accuracy level.

Abstract

\kdtree \citefriedman1976algorithm has long been deemed unsuitable for exact nearest-neighbor search in high dimensional data. The theoretical guarantees and the empirical performance of \kdtree do not show significant improvements over brute-force nearest-neighbor search in moderate to high dimensions. \kdtree has been used relatively more successfully for approximate search \citemuja2009flann but lack theoretical guarantees. In the article, we build upon randomized-partition trees \citedasgupta2013randomized to propose \kdtree based approximate search schemes with $O(d łog d + łog n)$ query time for data sets with n points in d dimensions and rigorous theoretical guarantees on the search accuracy. We empirically validate the search accuracy and the query time guarantees of our proposed schemes, demonstrating the significantly improved scaling for same level of accuracy.