[mlpack-git] [mlpack/mlpack] R+ tree implementation (#699)

[lozhnikov]

It seems I understood how git-cherry-pick works. If I understand correctly this branch will not be built until   the Hilbert R tree PR is merged.
Right now the R+ tree passes `RectangleTreeTest/RPlusTreeOverlapTest` and `RectangleTreeTest/RPlusTreeTraverserTest`.
I am not sure that the partition algorithm works correctly in general (I am not sure that the resulting nodes will not be overfull). The R+ tree paper enumerates four criteria (section 4 Packing Algorithm). I implemented the criterion "minimal total space coverage accrued by the two subregions". Maybe it is good idea to add a template parameter SweepType since there is another clear criterion "minimal number of rectangle splits". But I do not undestand how should work the criteria "nearest neghbors" and "minimal total x and y displacement" and the paper does not explain that.

Also I should use 
`double RPlusTreeSplit::SweepLeafNode(size_t axis, const TreeType* node,
    size_t fillFactor, ElemType& axisCut)`
instead of
`double RPlusTreeSplit::SweepLeafNode(size_t axis, const TreeType* node,
    size_t fillFactor, double& axisCut)`

The insertion algorithm tries to find the node that contains the point that is being inserted. If there are no such nodes the algorithm tries to enlarge a node. If the algorithm failed an empty node is added to the tree.
You can view, comment on, or merge this pull request online at:

  https://github.com/mlpack/mlpack/pull/699

-- Commit Summary --

  * R+ tree implementation

-- File Changes --

    M src/mlpack/core/tree/CMakeLists.txt (4)
    M src/mlpack/core/tree/rectangle_tree.hpp (2)
    A src/mlpack/core/tree/rectangle_tree/r_plus_tree_descent_heuristic.hpp (49)
    A src/mlpack/core/tree/rectangle_tree/r_plus_tree_descent_heuristic_impl.hpp (96)
    A src/mlpack/core/tree/rectangle_tree/r_plus_tree_split.hpp (95)
    A src/mlpack/core/tree/rectangle_tree/r_plus_tree_split_impl.hpp (441)
    M src/mlpack/core/tree/rectangle_tree/r_star_tree_split_impl.hpp (3)
    M src/mlpack/core/tree/rectangle_tree/r_tree_split_impl.hpp (2)
    M src/mlpack/core/tree/rectangle_tree/rectangle_tree_impl.hpp (4)
    M src/mlpack/core/tree/rectangle_tree/typedef.hpp (8)
    M src/mlpack/core/tree/rectangle_tree/x_tree_split_impl.hpp (3)
    M src/mlpack/tests/rectangle_tree_test.cpp (90)

-- Patch Links --

https://github.com/mlpack/mlpack/pull/699.patch
https://github.com/mlpack/mlpack/pull/699.diff

---
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/699
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://mailman.cc.gatech.edu/pipermail/mlpack-git/attachments/20160615/07348de8/attachment.html>