[mlpack] How to keep object when searching neighbors?

[Ryan Curtin]

On Wed, Jan 15, 2014 at 05:11:39PM +0800, Li Dong wrote:
> Dear MLPACK team,
> 
> I would like to use the NeighborSearch utility in my numerical
> advection scheme for finding out which mesh cells will be affected by
> a tracer parcel (measured by some shape function). In my codes, the
> tracer parcel is an object of class Tracer and the mesh cell is an
> object of class MeshCell. Both Tracer and MeshCell derive from class
> Point which has an attribute of space coordinate. To my current
> knowledge of MLPACK, it reads matrix in and writes matrix output, so I
> need to extract coordinates of both tracers and cells to form the
> input matrix, and construct the cell list for each tracer from the
> output matrix manually. I don’t think this is efficient, since the
> searching must be done every time step. Could I send the lists of
> Point in and get the lists of Point out?
> 
> I just started to use MLPACK, forgive my ignorance!

Hello Li,

The problem you're going to face with this is that no matter what you
are going to do, you'll have to rebuild the trees at each time step.
I think you could avoid the computational cost of copying your points
out of the Tracer and MeshCell classes.  Here is an idea...

I assume your Point class has some array of doubles in it, maybe
something like this:

class Point
{
  ...
  double* data;
};

The idea is that you construct some matrix object, and then set your
point's data pointer to the corresponding column in the matrix:

{
  const size_t numPoints, dimensionality;
  arma::mat dataMatrix(dimensionality, numPoints);
  Point* pointList = new Point[numPoints]; // Or use Tracer/MeshCell.
  for (size_t i = 0; i < numPoints; ++i)
    pointList.data = dataMatrix.colptr(i);
}

(you might need to cast the result of colptr() to a non-const pointer)

Anyway, by doing something like that, now when you update your points,
it's updating the data matrix directly.

Another option is to modify the NeighborSearch class to work with your
Point class instead of arma::mat, but that would be incredibly
tedious...

> P.S. I also studied locality-sensitive hashing, and I would like to
> know which searching method is more efficient.

A couple things:

 * LSH doesn't provide exact solutions; they are approximate.  Further,
   the bounds on the accuracy of the solution are probabilistic, and
   several parameters to LSH will affect its performance with respect to
   accuracy (number of hash tables, number of hash functions, bucket
   size, hash width, etc.).  However it is quite fast.

 * Tree-based search does provide exact nearest neighbors and is best in
   lower dimensions.  Personally I would look for something other than
   kd-tree nearest neighbor search when the dimensionality is greater
   than a few hundred.

Hope that helps.

Thanks,

Ryan

-- 
Ryan Curtin    | "Gentlemen, you can't fight in here!  This is the
ryan at ratml.org | War Room!" - President Muffley