[mlpack-git] [mlpack/mlpack] Vantage point tree (#708)

[Ryan Curtin]

I see, you are right that if we expand the bound to contain all of the child bounds, we end up with this situation.  Perhaps that behavior is useful.  But at the same time, for `MaxDistance()` (single-tree), I realized that we only require the maximum possible distance between the given point and any descendant points of the node.  So I commented out the code you referenced and re-ran single tree search and got the following results:

```
$ bin/mlpack_knn -r ~/datasets/corel.csv -v -k 3 -t vp -d d-vp.csv -n n-vp.csv --single
[INFO ] 53753034 node combinations were scored.
[INFO ] 301691470 base cases were calculated.
```

The results are still correct, and it runs faster, but we are still an order of magnitude off of kd-trees with the base cases (kd-trees do about 16.3M base cases with single-tree search).  It seems like this does not affect any test results either, so I think this is a valid change.  It might be worth noting somewhere, maybe as something new in TreeTraits or something, that the vantage point tree is not guaranteed to be such that the child HollowBallBounds are entirely contained within the parent HollowBallBounds---but it is always true that all descendant points of a node are contained within the bound (that is a required property of space trees in general).

Do you think this is a valid change to make?  And maybe there is somewhere I overlooked where it is possible to make the balls even tighter than just the bit I commented out?

---
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/mlpack/mlpack/pull/708#issuecomment-235342439
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://mailman.cc.gatech.edu/pipermail/mlpack-git/attachments/20160726/7a3c4233/attachment.html>