Efficient method for finding KNN of all nodes in a KD-Tree

Question

I'm currently attempting to find K Nearest Neighbor of all nodes of a balanced KD-Tree (with K=2).

My implementation is a variation of the code from the Wikipedia article and it's decently fast to find KNN of any node O(log N).

The problem lies with the fact that I need to find KNN of each node. Coming up with about O(N log N) if I iterate over each node and perform the search.

Is there a more efficient way to do this?

Solution 1

Depending on your needs, you may want to experiment with approximate techniques. For details, checkout Arya and Mount's work on the subject. A key paper is here. BigO complexity details are located in their '98 paper.

A graphical illustration of the work is shown below:

^{Source: http://www.cs.umd.edu/~mount/ANN/Images/annspeckle.gif}

I have used their library on very high dimensional datasets with hundreds of thousands of elements. It's faster than anything else I found. The library handles both exact and approximate searches. The package contains some CLI utilities that you can use to easily experiment with your dataset; and even visualize the kd-tree ( see above ).

FWIW: I used the R Bindings.

From ANN's manual:

...it has been shown by Arya and Mount [AM93b] and Arya, et al. [AMN+98] that if the user is willing to tolerate a small amount of error in the search (returning a point that may not be the nearest neighbor, but is not significantly further away from the query point than the true nearest neighbor) then it is possible to achieve significant improvements in run- ning time. ANN is a system for answering nearest neighbor queries both exactly and approximately.

Solution 2

I used cover tree for this problem. Here is the link: http://hunch.net/~jl/projects/cover_tree/cover_tree.html

In a data set for 50M size(All kNN query, k=100), cover tree took 5.5s for creation, and 120s for querying. Ann lib took 3.3s for creating the tree, and 138s for querying.

updated:The nearest neighbor is not a symmetric relation. Consider this:A(0,0) B(1,0) C(3,0). B is the nearest for C while C is not the nearest one for B

Solution 3

If the nodes themselves are query points, then the search time might be lower. You can start with backtracking stage and the first nodes tested are already near the query point. Then large areas of the tree can be pruned soon.

The nearest neighbor is a symmetric relation (if n1 is a nearest neighbor of n2, the same applies to n2) so you only need to search half the nodes skipping all the nodes already marked as nearest neighbors. Just an idea.

You can also try KD-Tree BBF (Best-Bin First) search, which will help you search the nearest nodes (bins) sooner. I have implemented this in C#, so write me if you are interested in the source code.

Of course, the actual running time depends on dimensionality, KD-Tree structure and distribution of points in your dataset.

Clustering of the points might also be appropriate.

Comments

[St. John Johnson]

Wow, thanks for the research, Ryan. Sadly I'm looking for accurate results. If KNN using a KD-Tree is limited at this speed, maybe I'm going about this search with the wrong data structures. Any alternate suggestions?

[Ryan Cox]

As the last sentence of that quote from their manual points out, you can do exact searches as well with this library. "ANN is a system for answering nearest neighbor queries both exactly and approximately"

[mrgloom]

Is all data needed to fit in RAM or only tree?

[Asher]

Approximate search is sometimes helpful. Try searching the likely path first and using a distance calculation that knows about hyperplanes and points along the path. If the final point isn't that close to any hyperplane then its usually the nearest neighbour.