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 '19 at 21:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.