[mlpack] How to keep object when searching neighbors?

[Ryan Curtin]

On Wed, Jan 15, 2014 at 11:45:51AM -0500, Ryan Curtin wrote:
> 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.

Sorry, I should clarify on this point.  I presume that in your
simulation, your Tracer and MeshCell points move or are somehow changed.
If this is true, then the kd-tree built on the points at one time step
is not valid for the points at the next time step.  The same is true of
locality-sensitive hashing, where your hashes have to be rebuilt.  There
isn't really a good way to "update" the tree so you can re-use it; the
ways I can think of to do that would highly degrade runtime performance
in each subsequent step or be so computationally expensive that it makes
more sense just to rebuild the tree.

In addition, building a kd-tree usually involves re-sorting the data and
takes O(N log N) time (when you have N points), so it may be true that
the time taken by the extra step of copying the data out of your Point
classes is not very significant when compared to the tree construction
time.

Anyway, those are just a few more thoughts.

Ryan

-- 
Ryan Curtin    | 
ryan at ratml.org | First there was darkness; then came the strangers.