knn-graph implementation in c sharp

[Rose-élegant]

I have to construct a K-nearest-neighbors graph, and I'm wondering what the fastest way would be of running through a list of nodes and connecting each one only to say, it's nearest five neighbors. My thought was that I would start at a node, iterate through the list of other nodes and keep the ones that are closest within an array, making sure that everything past the top n are discarded. Now, I could do this by just sorting a list and keeping the top n entries, but I would much rather keep less fewer things in memory and so I was wondering if there was a way to just have the final array and update that array as I iterate through, or if there is a more efficient way of generating a k nearest neighbors graph.

[César]

Hi Rose,

Perhaps the fastest way would be to use a KD-Tree. It is a data structure which you can query to obtain the nearest neighbors of a node. It still isn't available in the Accord.NET Framework, but I was already working on it before you asked! If you really need I could give a partial version.

Regards,

Cesar

[Rose-élegant]

hi Cesar,

            I have got some sign of hope from your reply as i could not found my answer anywhere else, thank you for quick reply, and i would really like try your solution so please share it with me.thank you again

Best Regards

[Rose-élegant]

Hi Cesar

              I hope to get the Kd trees soon, i have another question (sorry to bother you all the time), can we find something like only KNN search without classification or clustering something that i found in Matlab  and the link is http://www.mathworks.fr/fr/help/stats/knnsearch.html. would be of greater help.

              once we have the KNN indices could we apply any available graph libraries to draw it in c #, if you know any graph library please share.

Thank you

Regards

[César]

Hi Rose,

The kd-tree performs the kNN search without classification. It is a data structure that, once created over your data, allow you to query a point for its neighbors, either using a fixed number of neighbors on considering a given distance radius.

I am sending the kd-tree attached. It is not finished yet (lacks some documentation, polishing, etc) but it works.

To use it, create a KDTree from your data by calling

var tree = KDTree.FromData;

after that, you may query neighbors in the tree using 

tree.Nearest(yourpoint, distanceRadius)

or 

tree.Nearest(yourpoint, numberOfNeighbors)

Please see if it helps!

Best regards,

Cesar