2
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • $\begingroup$ You mean the k-Nearest Neighbors (k-NN) problem (k is not the dimension but the number of nearest neighbors)? $\endgroup$
    – Laxmana
    Feb 4, 2017 at 16:19
  • $\begingroup$ @Laxmana exactly. I have edited my question to correct this. $\endgroup$
    – Walter
    Feb 4, 2017 at 18:04
  • $\begingroup$ 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)$ ? $\endgroup$
    – Laxmana
    Feb 4, 2017 at 18:14

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$
    – Walter
    Feb 4, 2017 at 17:58
  • $\begingroup$ 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. $\endgroup$
    – Walter
    Feb 4, 2017 at 18:00
  • 1
    $\begingroup$ @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. $\endgroup$
    – D.W. ♦
    Feb 4, 2017 at 18:28
  • $\begingroup$ 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. $\endgroup$
    – Walter
    Feb 5, 2017 at 9:51
  • $\begingroup$ 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. $\endgroup$
    – Walter
    Feb 5, 2017 at 10:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.