[mlpack-git] [mlpack/mlpack] Use move semantics to set a given reference tree in NeighborSearch class. (#765)

Ryan Curtin notifications at github.com
Sat Aug 20 17:16:33 EDT 2016

I looked through this on the plane today and I think the biggest issue is providing a way for users to pass `oldFromNew` to the `NeighborSearch` class.  I disagree with this... a long explanation follows...

I believe that there are two ways one can use the `NeighborSearch` class: either you can pass in a dataset (possibly by reference where it may be copied, possibly by move constructor where it won't), and then the `NeighborSearch` class is responsible for the tree and everything associated with it.  Otherwise, you pass in a pre-constructed tree and the `NeighborSearch` class is not responsible for it.  One of the key aspects of "responsibility" here is that if the `NeighborSearch` class is responsible, then it must handle the `oldFromNew` mappings that _might_ exist if `RearrangesDataset == true`.  But `RearrangesDataset` is not always true, so there are only some cases where we need it.

Thus, if we allow the user to make `NeighborSearch` take control of the tree, this necessitates that *sometimes*, they will also have to pass `oldFromNew` in _with_ the tree; but not always.  We have no way to make a clean API that only has the right overload available depending on the `TreeType`.  (Yes, we can do SFINAE so only one is accepted, but an API with lots of `enable_if`s that is presented to the end user can be very confusing.  Armadillo handles this by basically hiding all of its internal details, but I don't like that strategy.)

So there is another option: we can hold the mappings inside of the `TreeType` and do away with `RearrangesDataset` entirely.  But this is problematic also: it means that every time we call `Point()`, we must apply the mapping... this will cause unacceptable slowdowns for anything that uses `BinarySpaceTree`.  So that's not really an option we can pursue.

There is a final option: do some crazy template overloading in order to hold `oldFromNew` inside of `BinarySpaceTree` but avoid de-mapping every time `Point()` is called.  I don't think that's a great idea though (and I'm not even sure it would work).  In addition it would increase the size of the `BinarySpaceTree` class which is something I'd like to try to avoid if possible.

The policy I have dealt with so far has worked like this: if the user passes in a dataset, then `NeighborSearch` manages the tree and the mappings, and the results you get are what you expect.  But if the user passes in the tree, then it is up to them to reverse the mappings.  This is potentially useful because it offers some speedup in the situation where the user has their own tree, but, say, aren't concerned with the ordering of their points and when their points are remapped, they don't care about the new ordering.

In my view, we can't know whether or not the user truly wants the points to be unmapped when they pass a tree, and I want to avoid the extra complexity of an API with a bunch of `Train()` overloads where some take a mappings vector and some don't.  So in my opinion, we can solve this by not allowing an overload like `Train(TreeType&&)` and instead only allowing `Train(TreeType&)` (implying that the `NeighborSearch` object does not own the mappings or tree and is not responsible for unmapping the results when `Search()` is called).  If we only allow `Train(TreeType&)`, we don't own the tree, so even if the tree does map points, we do not need to do the unmapping ourselves.

I hope my very long comment makes some amount of sense.  I am open to the concept of an eventual redesign, but I believe we must strongly pursue keeping the API simple enough for the average user but flexible enough for an advanced user to be able to get what they need done.  In this case having fewer overloads of `Train()` keeps it simple, but if an advanced user wants to do something tricky with a custom-built tree that maps points, then they can also figure out how to map the points back to their original indices.

You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://mailman.cc.gatech.edu/pipermail/mlpack-git/attachments/20160820/0a4d16a7/attachment.html>

More information about the mlpack-git mailing list