[mlpack-svn] [MLPACK] #371: KNN Search on the Torus

[MLPACK Trac]

#371: KNN Search on the Torus
-----------------------------+----------------------------------------------
  Reporter:  georgehagstrom  |        Owner:     
      Type:  defect          |       Status:  new
  Priority:  major           |    Milestone:     
 Component:  mlpack          |   Resolution:     
  Keywords:  Torus           |     Blocking:     
Blocked By:                  |  
-----------------------------+----------------------------------------------
Description changed by georgehagstrom:

Old description:

> I am attempting to use mlpack to find nearest neighbors on the 2-Torus. I
> wrote a metric class for the 2-Torus (basically the standard Euclidean
> metric on the 2-Torus) and attempted to use NeighborSerach in the most
> standard way, but in some cases it finds the wrong neighbors. My
> suspicion is that this is related to the use of the binary space tree,
> but I am uncertain.
>
> I have attached a sample program, minimalExample.cpp, and also
> torusMetric.hpp, which is the Metric class. In this program, I generate
> 98 random points on the set [.5,99.5]x[.5,99.5], distributed uniformly,
> and I place two additional points by hand, one at (.1,50) and the other
> at (99.9,50). These two points should be nearest neighbors no matter
> under my metric, with squared distance of .04.
>
> When I run my example program, depending on the random seed, these two
> points are not always paired together. When there are a large number of
> points clustered on the edge of the torus, many pairs are not found
> incorrectly.
>
> Two random seeds to try are 1 (which leads to one near neighbor found
> correctly and the other not) and 1000, which leads to neither point
> having its nearest neighbor found correctly.

New description:

 I am attempting to use mlpack to find nearest neighbors on the 2-Torus. I
 wrote a metric class for the 2-Torus (basically the standard Euclidean
 metric on the 2-Torus) and attempted to use NeighborSerach in the most
 standard way, but in some cases it finds the wrong neighbors. My suspicion
 is that this is related to the use of the binary space tree, but I am
 uncertain.

 I have attached a sample program, minimalExample.cpp, and also
 torusMetric.hpp, which is the Metric class. In this program, I generate 98
 random points on the set [.5,99.5]x[.5,99.5], distributed uniformly, and I
 place two additional points by hand, one at (.1,50) and the other at
 (99.9,50). These two points should be nearest neighbors no matter under my
 metric, with squared distance of .04.

 When I run my example program, depending on the random seed, these two
 points are not always paired together. When there are a large number of
 points clustered on the edge of the torus, many pairs are not found
 incorrectly.

 Two random seeds to try are 1 (which leads to one near neighbor found
 correctly and the other not) and 1000, which leads to neither point having
 its nearest neighbor found correctly.

 Thanks for any assistance!

--

-- 
Ticket URL: <http://trac.research.cc.gatech.edu/fastlab/ticket/371#comment:1>
MLPACK <www.fast-lab.org>
MLPACK is an intuitive, fast, and scalable C++ machine learning library developed at Georgia Tech.