What data structure has the best asymptotic running time for nearest-neighbor search on multidimensional data? I am interested in both preprocessing time and query time, but let's restrict attention to data structures with logarithmic average query time; how low can we make the average preprocessing time? By average, I mean the with respect to approximately uniformly distributed data.

Kd-trees give $O(n \log n)$ average preprocessing time with $O(\log n)$ query time. $O(\log n)$ query time is asymptotically optimal for deterministic algorithms, because $1$-nearest neighbor search can be used to solve the element distinctness problem. Likewise, $O(n \log n)$ preprocessing is asymptotically optimal since the kd-tree can then be used for sorting.

However, this does not prevent the existence of better randomized algorithms, which give the $k$ nearest neighbors with high probability. Indeed, for approximately uniformly distributed data, there may exist deterministic algorithms that are better.

Are there any randomized algorithms for multidimensional indexing that have a better (asymptotic) preprocessing time than kd-trees while still performing log-time queries?

  • 1
    $\begingroup$ I think there's a similar lower bound that also applies to randomized algorithms for element distinctness, assuming comparison-based algorithms; see en.wikipedia.org/wiki/…. I suspect the lower bound on comparison-based sorting algorithms can also be extended to randomized algorithms as well. So while I'm far from sure of this, I suspect the same $O(\log n)$ and $O(n \log n)$ lower bounds might apply to randomized algorithms (in the comparison-based model). $\endgroup$ – D.W. Feb 11 at 21:08

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.