k-d tree

[iglesias]

This is an entrance task for the fundamental machine learning algorithms GSoC project http://www.shogun-toolbox.org/page/Events/gsoc2014_ideas#fundamental.

The road map for this task could roughly be as follows:

• Implement a KDTree class that can be used for fast nearest neighbour search. The right place to put this class is inside the lib directory.
• Modify our current KNN class (it is inside the multiclass directory) so that the KDTree class in the previous point is usable. Note that currently our KNN supports two modes: brute force or cover tree, which can be selected with a boolean attribute of KNN. Once KDTree is added, it would be better to make this selection using an enumerated type.
• Compare the performance of the different approaches. For this comparison, it is most interesting to compare the kd-tree and the cover tree. This could be done extending the current KNN notebook http://shogun-toolbox.org/static/notebook/current/KNN.html.

Please, do not wait to have everything above ready to issue your pull request. Roughly, each of the points above is worth its own pull request. The smaller a pull request is, the easier it is to get it merged. However, note also that they have to be fully compilable and add some functionality.

[iglesias]

Feel free to write your name below if you are working on this task! This way we avoid wasting manpower on the same algorithm.

[dhruv13J]

@iglesias: I'm attempting this :-)

[punnu]

@iglesias: already working on it :)

[dhruv13J]

@punnu: I've only just begun... If you already implemented the kdtree, I think i should move on to something else...

[punnu]

@dhruv13J: sorry for messaging lately.. i started working on it last night. So, if you are ahead of me, i can move to another task.

[dhruv13J]

@punnu: no problem! I've begun recently too... maybe we can decide based on the first PR ;-) ... I'm attempting this seriously for now...

[vigsterkr]

please note that before you start reinventing the wheel there are some libraries that extensively worked with this topic:

• http://www.cs.ubc.ca/research/flann/
• https://code.google.com/p/nanoflann/

nanoflann is great because it's like eigen, i.e. header only based and from the statistics seems to be better than flann itself...

[dhruv13J]

@iglesias What are your suggestions about using nanoflann?

[iglesias]

Integrating nanoflann might be another possibility indeed. I am not familiarized with it at all so I will have a look, but feel free to go on your own and study whether we could integrate, bundle it, etc.

[dhruv13J]

@iglesias: Bundling is an option because it is a single header file, with a BSD licence. I will try this approach first.

[dhruv13J]

@iglesias @vigsterkr: Please take a look, I haven't made changes to KNN.h yet, because I'm still testing it. Here's the test program (based on KNN example under undocumented libshogun examples): https://gist.github.com/dhruv13J/9567939

[arman-z]

Hi, please take a look of my simple implementation of KD-tree from scratch. #2095

[arman-z]

https://github.com/armanform/shogun/commit/41635990f69ede73a04d60b4da108ee1149714ef
Hi, this is my KNN class with kd tree. Bruteforce integration with KNN.h and KNN.cpp

[iglesias]

@armanform, could you please update #2095 instead? Just get rid of the previous commits in that pull request and issue the one you have linked to in your previous comments.

[arman-z]

Ok, I've some problem to reverse commits, so I opened new pull request with only the last commit
#2117

[vigsterkr]

@iglesias @mazumdarparijat this is done, or?

[iglesias]

I think this took eventually a different path since we have the kd-tree but it is not usable as the cover tree is from knn. Still, it is possible to do knn classification with the kd-tree using an instance of the tree directly. Is that right, @mazumdarparijat?

I didn't see any benchmark comparing cover tree and kd-tree.

[vigsterkr]

no the question was is kd-tree implemented in shogun?

[vigsterkr]

yes it is. fixed

[mazumdarparijat]

@iglesias We shall make it possible to access kd-tree/ball-tree from knn. I will have to look at the knn code. Once the integration is done, we can compare kd-tree and cover tree. I see that cover tree implementation is infused with the knn implementation. There is no separate class.

[iglesias]

The cover tree implementation is under lib. JLCoverTree is the class.

[mazumdarparijat]

ohk! I will look at this after Aug 5. Not as part of GSoC though! ;-)