[mlpack-git] [mlpack/mlpack] Universal B tree implementation (#746)

[lozhnikov]

I implemented the UB tree. Despite the tree passes all tests from `ub_tree_test.cpp` including the test that verifies `MinDistance()` and `MaxDistance()`, `KNNTest/KNNModelTest` sometimes fails, I am trying to fix that.

The bound of the UB tree consists of a number of hyperrectangles in such a way that children of the UB tree do not overlap each other. However, I realized that the calculation of the distance between two nodes requires a lot of operations. So, I had to add some limitations on the number of hyperrectangles.

The tree sorts the dataset before the split process since the tree introduces an ordering in multidimensional space and all points are inserted into the tree according to that ordering. Probably it is better to choose a number of distinct samples and to split according the median. 
You can view, comment on, or merge this pull request online at:

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

-- Commit Summary --

  * Universal B tree implementation

-- File Changes --

    M src/mlpack/core/tree/CMakeLists.txt (5)
    A src/mlpack/core/tree/address.hpp (187)
    M src/mlpack/core/tree/binary_space_tree.hpp (1)
    M src/mlpack/core/tree/binary_space_tree/traits.hpp (17)
    M src/mlpack/core/tree/binary_space_tree/typedef.hpp (8)
    A src/mlpack/core/tree/binary_space_tree/ub_tree_split.hpp (64)
    A src/mlpack/core/tree/binary_space_tree/ub_tree_split_impl.hpp (301)
    M src/mlpack/core/tree/bounds.hpp (1)
    A src/mlpack/core/tree/cellbound.hpp (211)
    A src/mlpack/core/tree/cellbound_impl.hpp (803)
    M src/mlpack/methods/neighbor_search/kfn_main.cpp (14)
    M src/mlpack/methods/neighbor_search/knn_main.cpp (14)
    M src/mlpack/methods/neighbor_search/ns_model.hpp (6)
    M src/mlpack/methods/neighbor_search/ns_model_impl.hpp (6)
    M src/mlpack/tests/CMakeLists.txt (1)
    M src/mlpack/tests/aknn_test.cpp (16)
    M src/mlpack/tests/knn_test.cpp (12)
    A src/mlpack/tests/ub_tree_test.cpp (334)

-- Patch Links --

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