[mlpack] Approximate Nearest Neighbour - Gsoc 2016

[Ryan Curtin]

On Wed, Mar 02, 2016 at 07:43:48PM +0530, Jayaganesh Kalyanasundaram wrote:
> Hi sir,
> 
> This is Jayaganesh K from IIIT-H(International Institute of
> Information Technology-Hyderabad) with CGPA-9.81 . I'm a very
> enthusiastic Coder with good skills in C++/Python & CV & Machine
> Learning.
> 
> ...
>
> I'm very much thrilled with "Approximate Nearest Neighbor Search"
> project and would like to contribute and take part in GSoC 2016 in the
> ORG-MLPACK in this domain. Further MLPACK ORG is very close to my
> skill set and and my liking and I'd be more than loving to contribute
> to it.

Hi there Jayaganesh,

Thanks for getting in touch.

The approximate nearest neighbor search project is best accomplished
after spending some good amount of time reading papers.  With the right
knowledge, I think the project is easy, but maybe the knowledge takes a
lot of time to get. :)

You should definitely be familiar with dual-tree algorithms and how they
are used for nearest-neighbor search.  Here is a paper that details the
abstractions used by mlpack for dual-tree algorithms:

"Tree-independent dual-tree algorithms"
http://www.ratml.org/pub/pdf/2013tree.pdf

Once you understand that, it may be useful to look through the existing
nearest neighbor search code in src/mlpack/methods/neighbor_search/.

Then, you should also be familiar with other nearest neighbor search
(and approximate nearest neighbor search) literature.  Here are a bunch
of papers:

"An optimal algorithm for approximate nearest neighbor searching in
fixed dimensions", S. Arya, D.M. Mount, N.S. Netanyahu, R. Silverman,
A.Y. Wu.
http://www.cs.montana.edu/courses/spring2005/580/papers/arya.pdf

"Fast Approximate Nearest Neighbors with Automatic Algorithm
Configuration", M. Muja, D. Lowe.
http://www.cs.ubc.ca/research/flann/uploads/FLANN/flann_visapp09.pdf

"An investigation of pracitcal approximate nearest neighbor algorithms",
T. Liu, A.W. Moore, A.G. Gray, K. Yang.
http://machinelearning.wustl.edu/mlpapers/paper_files/NIPS2005_187.pdf

It may also be helpful to be familiar with LSH and related other
techniques for nearest neighbor search, since it would be useful to
compare against those in your implementation.

I hope this is helpful.  Please let me know if I can clarify anything.

Thanks,

Ryan

-- 
Ryan Curtin    | "Hey, tell me the truth... are we still in the
ryan at ratml.org | game?" - The Chinese Waiter