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?