[mlpack-git] [mlpack/mlpack] Hilbert R tree (#664)

[lozhnikov]

I think the Hilbert R tree is almost done and it's time to make PR.

Known issues:
1. I am not sure of the `DiscreteHilbertValue` class. It uses `std::list` for the local dataset.
`std::list<arma::Col<uint64_t>> *localDataset;`
I think `std::vector` or `arma::Mat` may be much faster since `std::list` can not reserve memory.
And maybe the type of the `arma::Col` should be a template parameter.
2. The RecursiveHilbertValue class is very slow. I think it is better to utilize at each step at least 32 bits instead of one.
3. Some constructions like `root->AuxiliaryInfo().LargestHilbertValue().LargestValue()` are long. As for me it is better to correct them.

Now the tree passes RectangleTreeTest/(DiscreteHilbertRTreeTraverserTest, RecursiveHilbertRTreeTraverserTest, DiscreteHilbertOrderingTest, RecursiveHilbertOrderingTest) tests. I'll try to think out other tests.
You can view, comment on, or merge this pull request online at:

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

-- Commit Summary --

  * Added initial support for Hilbert R trees (split and descent heuristic design).
  * Move tree-specific information to a new class (AuxiliaryInformationType).
  * A lot of changes. Implemented two approaches in order to compare points.
  * Added a bit of documentation.
  * Hilbert R tree fixes.

-- File Changes --

    M src/mlpack/core/tree/CMakeLists.txt (12)
    M src/mlpack/core/tree/rectangle_tree.hpp (7)
    A src/mlpack/core/tree/rectangle_tree/discrete_hilbert_value.hpp (200)
    A src/mlpack/core/tree/rectangle_tree/discrete_hilbert_value_impl.hpp (399)
    M src/mlpack/core/tree/rectangle_tree/dual_tree_traverser.hpp (7)
    M src/mlpack/core/tree/rectangle_tree/dual_tree_traverser_impl.hpp (16)
    A src/mlpack/core/tree/rectangle_tree/hilbert_r_tree_auxiliary_information.hpp (119)
    A src/mlpack/core/tree/rectangle_tree/hilbert_r_tree_auxiliary_information_impl.hpp (177)
    A src/mlpack/core/tree/rectangle_tree/hilbert_r_tree_descent_heuristic.hpp (59)
    A src/mlpack/core/tree/rectangle_tree/hilbert_r_tree_descent_heuristic_impl.hpp (59)
    M src/mlpack/core/tree/rectangle_tree/hilbert_r_tree_split.hpp (85)
    M src/mlpack/core/tree/rectangle_tree/hilbert_r_tree_split_impl.hpp (334)
    A src/mlpack/core/tree/rectangle_tree/no_auxiliary_information.hpp (84)
    M src/mlpack/core/tree/rectangle_tree/r_star_tree_descent_heuristic.hpp (13)
    M src/mlpack/core/tree/rectangle_tree/r_star_tree_descent_heuristic_impl.hpp (9)
    M src/mlpack/core/tree/rectangle_tree/r_star_tree_split.hpp (24)
    M src/mlpack/core/tree/rectangle_tree/r_star_tree_split_impl.hpp (35)
    M src/mlpack/core/tree/rectangle_tree/r_tree_descent_heuristic.hpp (13)
    M src/mlpack/core/tree/rectangle_tree/r_tree_descent_heuristic_impl.hpp (7)
    M src/mlpack/core/tree/rectangle_tree/r_tree_split.hpp (29)
    M src/mlpack/core/tree/rectangle_tree/r_tree_split_impl.hpp (44)
    M src/mlpack/core/tree/rectangle_tree/rectangle_tree.hpp (18)
    M src/mlpack/core/tree/rectangle_tree/rectangle_tree_impl.hpp (336)
    A src/mlpack/core/tree/rectangle_tree/recursive_hilbert_value.hpp (227)
    A src/mlpack/core/tree/rectangle_tree/recursive_hilbert_value_impl.hpp (245)
    M src/mlpack/core/tree/rectangle_tree/single_tree_traverser.hpp (7)
    M src/mlpack/core/tree/rectangle_tree/single_tree_traverser_impl.hpp (16)
    M src/mlpack/core/tree/rectangle_tree/traits.hpp (7)
    M src/mlpack/core/tree/rectangle_tree/typedef.hpp (40)
    A src/mlpack/core/tree/rectangle_tree/x_tree_auxiliary_information.hpp (158)
    M src/mlpack/core/tree/rectangle_tree/x_tree_split.hpp (62)
    M src/mlpack/core/tree/rectangle_tree/x_tree_split_impl.hpp (94)
    M src/mlpack/tests/rectangle_tree_test.cpp (145)

-- Patch Links --

https://github.com/mlpack/mlpack/pull/664.patch
https://github.com/mlpack/mlpack/pull/664.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/664
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://mailman.cc.gatech.edu/pipermail/mlpack-git/attachments/20160601/0769f51b/attachment-0001.html>