# What is the state of the art for k nearest neighbour search?

I'm not an computer scientist, but still use/have an algorithm to find the $k$ nearest neighbours from a cloud of $N$ points in $d$ (my case $d=3$) dimensional space using some distance measure (in my case Euclidean). I had some look at the literature and it appears that the standard is J. H. Friedman, J. L. Bentley, and R. A. Finkel. An algorithm for finding best matches in logarithmic expected time. ACM Trans. Math. Softw., 3:209–226, 1977, which is a root-first tree traversal on a kd tree. This algorithm has complexity $O(dk\log N)$ for each search (after the tree has been built at cost $O(dN\log N)$). I wonder whether this is still the state of the art.

The reason I'm asking is that my own algorithm is different (also using a tree) and has (I believe) average costs of $O(dk)$ per search (but still worst case $O(dk\log N)$), provided the query point is a member of the cloud. So I was wondering whether it's perhaps worth publishing.

• You mean the k-Nearest Neighbors (k-NN) problem (k is not the dimension but the number of nearest neighbors)? – Laxmana Feb 4 '17 at 16:19
• @Laxmana exactly. I have edited my question to correct this. – Walter Feb 4 '17 at 18:04
• The $O(k)$ seems very good. So the algorithm can answer the Nearest neighbor in $O(1)$ (for $k = 1$) ? Or you mean $O(N)$ ? – Laxmana Feb 4 '17 at 18:14

It seems hard to imagine that your claimed running time is correct, for a method that works in an arbitrary number of dimensions. It sounds like you are claiming that your data structures works in an arbitrary number of dimensions ($n$), but the running time does not depend on the dimension ($n$). That seems unlikely; nearest neighbor search is known to be hard to solve in high dimensions (the so-called curse of dimensionality).

Alternatively, if you meant that your scheme works only in 3 dimensions, then that is an important caveat that needs to be mentioned. Being able to find the nearest neighbor in 3D in $O(1)$ time would be an impressive result; I'm not aware of any data structure that is known to have this worst-case running time.

Yes, a k-d tree is a standard data structure for this task, when you are working in 3 dimensions. There are also generalizations and related data structures; see metric trees, binary space partitioning trees and octrees. R-trees and R*-trees can be used if the set of points are changing.

Without knowing how your algorithms works, it's hard to give a definitive answer whether it is worth publishing. To figure out, a good starting point would be to familiarize yourself with the published and known algorithms and see if your idea still seems to be better than all known schemes. If you're still not sure, make ask a new question here with the specifics of your algorithm and what your specific uncertainty is.

• Thanks for your effort. I was not asking about the tree, but about the search algorithm itself (using the tree), which can be adapted to any tree structure imposing a spatial ordering of the points. – Walter Feb 4 '17 at 17:58
• familiarize yourself with the published and known algorithms which are? (could you provide some pointers?) The one I was quoting appears state of the art, the relevant CGAL module implements it, for example. – Walter Feb 4 '17 at 18:00
• @Walter, I think you've misunderstood my answer. I am describing search algorithms; something like a metric tree is a combination of a tree-based data structure and a search algorithm for answering nearest neighbor queries. Just because one library implements a particular algorithm doesn't necessarily mean that that algorithm has the best asymptotic running time of all algorithms in the literature. An algorithm might be chosen for other reasons, e.g., simplicity of implementation, ease of maintenance or extension, cache friendliness, etc. Anyway, see revised answer. – D.W. Feb 4 '17 at 18:28
• For finding the nearest neighbour of one of the points (not an arbitrary search position), my algorithm has worst case complexity $O(\ln N)$ but for most points is faster. But, I have not experimented with >3 dimensions, and I didn't mean to claim that running time does not scale with number $n$ of dimensions. – Walter Feb 5 '17 at 9:51
• I'm really interested (and my algorithm is optimized for) finding the nearest $k\gg1$ neighbors for query points selected from the cloud of data points. I.e. not for an arbitrary query that may be far from the cloud. – Walter Feb 5 '17 at 10:08