[mlpack] How to keep object when searching neighbors?

[Li Dong]

Hi Ryan,

Thank you for your thorough explanation! I will give MLPACK a try. In my simulation, I need two kinds of neighbor searching:

Transferring information between Tracer and MeshCell. The MeshCell is fixed, so I think the tree is fixed too.
Communication among tracers (e.g., compute physical diffusion). The tree for Tracer will be changed each time step.

In addition, I need the mesh cell neighbors of a tracer that are within a specified radius (say R). Actually, after finding them, I also need to use some shape (or kernel) function to calculate weights. Does MLPACK provide such searching without just returning K nearest neighbors? Or do I need to make some changes on the template parameter (NearestNeighborSearch)? Could I use the shape function directly (There may be problem, since the shape function depends on the tracer’s properties.)?

Best regards,

Li

On 2014年1月16日, at 上午12:54, Ryan Curtin <gth671b at mail.gatech.edu> wrote:

> 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.

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cc.gatech.edu/pipermail/mlpack/attachments/20140116/9f464046/attachment-0003.html>