# Best asymptotic randomized multidimensional index?

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?

• 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). – D.W. Feb 11 at 21:08