[mlpack-git] master: Merge remote-tracking branch 'upstream/master' into r_plus_tree Fix conflicts (857cca0)

gitdub at mlpack.org gitdub at mlpack.org
Mon Jun 27 12:42:09 EDT 2016


Repository : https://github.com/mlpack/mlpack
On branch  : master
Link       : https://github.com/mlpack/mlpack/compare/6147ed01bab6eadcd6a5e796e259a6afacae4662...e0fd69006b17a845f066ea4de1e205fc0922739d

>---------------------------------------------------------------

commit 857cca05ea9cfa0617b2070dc71183e5c0ca3a0f
Merge: da4b598 479eca0
Author: Mikhail Lozhnikov <lozhnikovma at gmail.com>
Date:   Mon Jun 27 19:42:09 2016 +0300

    Merge remote-tracking branch 'upstream/master' into r_plus_tree
    Fix conflicts


>---------------------------------------------------------------

857cca05ea9cfa0617b2070dc71183e5c0ca3a0f
 .appveyor.yml                                      |  12 +-
 .gitignore                                         |   5 -
 CMakeLists.txt                                     |   2 +-
 HISTORY.md                                         |   9 +-
 LICENSE.txt                                        |  12 +-
 README.md                                          |   2 +-
 src/mlpack/core.hpp                                |   2 +-
 src/mlpack/core/arma_extend/CMakeLists.txt         |   4 -
 src/mlpack/core/arma_extend/Mat_extra_bones.hpp    |  10 +
 src/mlpack/core/arma_extend/Mat_extra_meat.hpp     |  10 +
 src/mlpack/core/arma_extend/README.md              |  23 +
 src/mlpack/core/arma_extend/SpMat_extra_bones.hpp  |  40 +-
 src/mlpack/core/arma_extend/SpMat_extra_meat.hpp   | 323 +-----------
 src/mlpack/core/arma_extend/arma_extend.hpp        |   4 -
 src/mlpack/core/arma_extend/fn_ind2sub.hpp         |   8 +
 src/mlpack/core/arma_extend/hdf5_misc.hpp          |  11 +
 src/mlpack/core/arma_extend/operator_minus.hpp     |  10 +
 src/mlpack/core/arma_extend/promote_type.hpp       |  50 --
 src/mlpack/core/arma_extend/restrictors.hpp        |  22 -
 src/mlpack/core/arma_extend/traits.hpp             |  49 --
 src/mlpack/core/arma_extend/typedef.hpp            |  30 --
 src/mlpack/core/boost_backport/LICENSE.txt         |  23 +
 src/mlpack/core/boost_backport/README.md           |  11 +-
 .../unordered_collections_load_imp.hpp             |   3 +
 .../unordered_collections_save_imp.hpp             |   3 +
 src/mlpack/core/boost_backport/unordered_map.hpp   |   5 +-
 src/mlpack/core/data/CMakeLists.txt                |   1 +
 src/mlpack/core/data/binarize.hpp                  |  99 ++++
 src/mlpack/core/optimizers/lbfgs/lbfgs.hpp         |   4 +-
 src/mlpack/core/tree/CMakeLists.txt                |   2 -
 src/mlpack/core/tree/rectangle_tree.hpp            |   1 -
 .../tree/rectangle_tree/discrete_hilbert_value.hpp |  88 ++--
 .../rectangle_tree/discrete_hilbert_value_impl.hpp | 111 ++--
 .../hilbert_r_tree_auxiliary_information.hpp       |   3 -
 .../hilbert_r_tree_auxiliary_information_impl.hpp  |  16 -
 .../tree/rectangle_tree/hilbert_r_tree_split.hpp   |   2 +-
 .../rectangle_tree/hilbert_r_tree_split_impl.hpp   |  25 +-
 .../rectangle_tree/no_auxiliary_information.hpp    |  48 +-
 .../core/tree/rectangle_tree/rectangle_tree.hpp    |  29 +-
 .../tree/rectangle_tree/rectangle_tree_impl.hpp    |   7 +-
 .../rectangle_tree/recursive_hilbert_value.hpp     | 219 --------
 .../recursive_hilbert_value_impl.hpp               | 347 -------------
 src/mlpack/core/tree/rectangle_tree/typedef.hpp    |  39 +-
 .../x_tree_auxiliary_information.hpp               |  48 +-
 src/mlpack/core/util/cli.cpp                       |  57 +--
 src/mlpack/core/util/cli.hpp                       |  18 +-
 src/mlpack/core/util/cli_impl.hpp                  |  45 +-
 src/mlpack/methods/ann/ffn.hpp                     |  24 +-
 src/mlpack/methods/ann/rnn.hpp                     |  20 +-
 src/mlpack/methods/cf/cf_main.cpp                  |   2 +-
 src/mlpack/methods/det/det_main.cpp                |   2 +-
 src/mlpack/methods/emst/emst_main.cpp              |  25 +-
 src/mlpack/methods/gmm/gmm_generate_main.cpp       |  11 +-
 src/mlpack/methods/gmm/gmm_probability_main.cpp    |  17 +-
 src/mlpack/methods/hmm/hmm_generate_main.cpp       |  16 +-
 src/mlpack/methods/hmm/hmm_train_main.cpp          |   7 +-
 src/mlpack/methods/hmm/hmm_viterbi_main.cpp        |  13 +-
 .../hoeffding_trees/hoeffding_tree_main.cpp        |  45 +-
 src/mlpack/methods/lars/lars_main.cpp              |  37 +-
 .../linear_regression/linear_regression_main.cpp   |  54 +-
 src/mlpack/methods/lsh/lsh_main.cpp                |  23 +-
 src/mlpack/methods/lsh/lsh_search.hpp              |  71 ++-
 src/mlpack/methods/lsh/lsh_search_impl.hpp         | 258 ++++++----
 src/mlpack/methods/mvu/mvu_main.cpp                |  18 +-
 src/mlpack/methods/neighbor_search/CMakeLists.txt  |  30 +-
 src/mlpack/methods/neighbor_search/kfn_main.cpp    |  28 +-
 src/mlpack/methods/neighbor_search/knn_main.cpp    |  14 +-
 .../methods/neighbor_search/neighbor_search.hpp    |  19 +-
 .../neighbor_search/neighbor_search_impl.hpp       |  32 +-
 .../neighbor_search/neighbor_search_rules.hpp      |   4 +
 .../neighbor_search/neighbor_search_rules_impl.hpp |  14 +-
 src/mlpack/methods/neighbor_search/ns_model.hpp    | 231 ++++++++-
 .../methods/neighbor_search/ns_model_impl.hpp      | 558 ++++++++++-----------
 .../sort_policies/furthest_neighbor_sort.cpp       |   4 +-
 .../sort_policies/furthest_neighbor_sort.hpp       |  17 +
 .../sort_policies/nearest_neighbor_sort.hpp        |  15 +
 src/mlpack/methods/pca/pca_main.cpp                |   7 +-
 src/mlpack/methods/perceptron/perceptron_main.cpp  |  15 +-
 src/mlpack/methods/preprocess/CMakeLists.txt       |   1 +
 .../preprocess/preprocess_binarize_main.cpp        |  85 ++++
 .../methods/preprocess/preprocess_split_main.cpp   |  69 +--
 src/mlpack/methods/radical/radical_main.cpp        |   6 +-
 src/mlpack/methods/rann/CMakeLists.txt             |  20 +-
 .../rann/{allkrann_main.cpp => krann_main.cpp}     |   6 +-
 src/mlpack/methods/rann/ra_typedef.hpp             |  43 +-
 .../softmax_regression/softmax_regression_main.cpp |  78 ++-
 src/mlpack/tests/CMakeLists.txt                    |   5 +-
 src/mlpack/tests/activation_functions_test.cpp     |   2 +-
 src/mlpack/tests/ada_delta_test.cpp                |   2 +-
 src/mlpack/tests/adaboost_test.cpp                 |   2 +-
 src/mlpack/tests/adam_test.cpp                     |   2 +-
 src/mlpack/tests/akfn_test.cpp                     | 240 +++++++++
 src/mlpack/tests/aknn_test.cpp                     | 400 +++++++++++++++
 src/mlpack/tests/arma_extend_test.cpp              |   2 +-
 src/mlpack/tests/armadillo_svd_test.cpp            |   2 +-
 src/mlpack/tests/aug_lagrangian_test.cpp           |   2 +-
 src/mlpack/tests/binarize_test.cpp                 |  66 +++
 src/mlpack/tests/cf_test.cpp                       |   2 +-
 src/mlpack/tests/cli_test.cpp                      |   2 +-
 src/mlpack/tests/convolution_test.cpp              |   2 +-
 src/mlpack/tests/convolutional_network_test.cpp    |   2 +-
 src/mlpack/tests/cosine_tree_test.cpp              |   2 +-
 src/mlpack/tests/decision_stump_test.cpp           |   2 +-
 src/mlpack/tests/det_test.cpp                      |   2 +-
 src/mlpack/tests/distribution_test.cpp             |   2 +-
 src/mlpack/tests/emst_test.cpp                     |   2 +-
 src/mlpack/tests/fastmks_test.cpp                  |   2 +-
 src/mlpack/tests/feedforward_network_test.cpp      |   2 +-
 src/mlpack/tests/gmm_test.cpp                      |   2 +-
 src/mlpack/tests/hmm_test.cpp                      |   2 +-
 src/mlpack/tests/hoeffding_tree_test.cpp           |   2 +-
 src/mlpack/tests/ind2sub_test.cpp                  |   2 +-
 src/mlpack/tests/init_rules_test.cpp               |   2 +-
 src/mlpack/tests/kernel_pca_test.cpp               |   2 +-
 src/mlpack/tests/kernel_test.cpp                   |   2 +-
 src/mlpack/tests/kernel_traits_test.cpp            |   2 +-
 src/mlpack/tests/kfn_test.cpp                      |   2 +-
 src/mlpack/tests/kmeans_test.cpp                   |   2 +-
 src/mlpack/tests/knn_test.cpp                      |   6 +-
 ...krann_search_test.cpp => krann_search_test.cpp} |  12 +-
 src/mlpack/tests/lars_test.cpp                     |   2 +-
 src/mlpack/tests/layer_traits_test.cpp             |   2 +-
 src/mlpack/tests/lbfgs_test.cpp                    |   2 +-
 src/mlpack/tests/lin_alg_test.cpp                  |   2 +-
 src/mlpack/tests/linear_regression_test.cpp        |   2 +-
 src/mlpack/tests/load_save_test.cpp                |   2 +-
 src/mlpack/tests/local_coordinate_coding_test.cpp  |   2 +-
 src/mlpack/tests/log_test.cpp                      |   2 +-
 src/mlpack/tests/logistic_regression_test.cpp      |   2 +-
 src/mlpack/tests/lrsdp_test.cpp                    |   2 +-
 src/mlpack/tests/lsh_test.cpp                      | 122 ++++-
 src/mlpack/tests/lstm_peephole_test.cpp            |   2 +-
 src/mlpack/tests/math_test.cpp                     |   2 +-
 src/mlpack/tests/matrix_completion_test.cpp        |   2 +-
 src/mlpack/tests/maximal_inputs_test.cpp           |   2 +-
 src/mlpack/tests/mean_shift_test.cpp               |   2 +-
 src/mlpack/tests/metric_test.cpp                   |   2 +-
 src/mlpack/tests/minibatch_sgd_test.cpp            |   2 +-
 src/mlpack/tests/mlpack_test.cpp                   |   2 +-
 src/mlpack/tests/nbc_test.cpp                      |   2 +-
 src/mlpack/tests/nca_test.cpp                      |   2 +-
 src/mlpack/tests/network_util_test.cpp             |   2 +-
 src/mlpack/tests/nmf_test.cpp                      |   2 +-
 src/mlpack/tests/nystroem_method_test.cpp          |   2 +-
 src/mlpack/tests/pca_test.cpp                      |   2 +-
 src/mlpack/tests/perceptron_test.cpp               |   2 +-
 src/mlpack/tests/performance_functions_test.cpp    |   2 +-
 src/mlpack/tests/pooling_rules_test.cpp            |   2 +-
 src/mlpack/tests/quic_svd_test.cpp                 |   2 +-
 src/mlpack/tests/radical_test.cpp                  |   2 +-
 src/mlpack/tests/range_search_test.cpp             |   2 +-
 src/mlpack/tests/rectangle_tree_test.cpp           | 165 ++++--
 src/mlpack/tests/recurrent_network_test.cpp        |   2 +-
 src/mlpack/tests/regularized_svd_test.cpp          |   2 +-
 src/mlpack/tests/rmsprop_test.cpp                  |   2 +-
 src/mlpack/tests/sa_test.cpp                       |   2 +-
 src/mlpack/tests/sdp_primal_dual_test.cpp          |   2 +-
 src/mlpack/tests/serialization.hpp                 |   2 +-
 src/mlpack/tests/serialization_test.cpp            |  14 +-
 src/mlpack/tests/sgd_test.cpp                      |   2 +-
 src/mlpack/tests/softmax_regression_test.cpp       |   2 +-
 src/mlpack/tests/sort_policy_test.cpp              |   2 +-
 src/mlpack/tests/sparse_autoencoder_test.cpp       |   2 +-
 src/mlpack/tests/sparse_coding_test.cpp            |   2 +-
 src/mlpack/tests/split_data_test.cpp               |   2 +-
 src/mlpack/tests/svd_batch_test.cpp                |   2 +-
 src/mlpack/tests/svd_incremental_test.cpp          |   2 +-
 src/mlpack/tests/termination_policy_test.cpp       |   2 +-
 ...d_boost_test_definitions.hpp => test_tools.hpp} |  14 +-
 src/mlpack/tests/tree_test.cpp                     |   2 +-
 src/mlpack/tests/tree_traits_test.cpp              |   2 +-
 src/mlpack/tests/union_find_test.cpp               |   2 +-
 172 files changed, 2807 insertions(+), 2220 deletions(-)

diff --cc src/mlpack/core/tree/CMakeLists.txt
index 0a46a1e,0399e84..a7c62e4
--- a/src/mlpack/core/tree/CMakeLists.txt
+++ b/src/mlpack/core/tree/CMakeLists.txt
@@@ -59,24 -59,8 +59,22 @@@ set(SOURCE
    rectangle_tree/hilbert_r_tree_split_impl.hpp
    rectangle_tree/hilbert_r_tree_auxiliary_information.hpp
    rectangle_tree/hilbert_r_tree_auxiliary_information_impl.hpp
-   rectangle_tree/recursive_hilbert_value.hpp
-   rectangle_tree/recursive_hilbert_value_impl.hpp
    rectangle_tree/discrete_hilbert_value.hpp
    rectangle_tree/discrete_hilbert_value_impl.hpp
 +  rectangle_tree/r_plus_tree_descent_heuristic.hpp
 +  rectangle_tree/r_plus_tree_descent_heuristic_impl.hpp
 +  rectangle_tree/minimal_coverage_sweep.hpp
 +  rectangle_tree/minimal_coverage_sweep_impl.hpp
 +  rectangle_tree/minimal_splits_number_sweep.hpp
 +  rectangle_tree/minimal_splits_number_sweep_impl.hpp
 +  rectangle_tree/r_plus_tree_split.hpp
 +  rectangle_tree/r_plus_tree_split_impl.hpp
 +  rectangle_tree/r_plus_tree_split_policy.hpp
 +  rectangle_tree/r_plus_plus_tree_descent_heuristic.hpp
 +  rectangle_tree/r_plus_plus_tree_descent_heuristic_impl.hpp
 +  rectangle_tree/r_plus_plus_tree_split_policy.hpp
 +  rectangle_tree/r_plus_plus_tree_auxiliary_information.hpp
 +  rectangle_tree/r_plus_plus_tree_auxiliary_information_impl.hpp
    statistic.hpp
    traversal_info.hpp
    tree_traits.hpp
diff --cc src/mlpack/core/tree/rectangle_tree.hpp
index a31b75b,c2ff9bb..6ed68ec
--- a/src/mlpack/core/tree/rectangle_tree.hpp
+++ b/src/mlpack/core/tree/rectangle_tree.hpp
@@@ -28,16 -28,7 +28,15 @@@
  #include "rectangle_tree/hilbert_r_tree_descent_heuristic.hpp"
  #include "rectangle_tree/hilbert_r_tree_split.hpp"
  #include "rectangle_tree/hilbert_r_tree_auxiliary_information.hpp"
- #include "rectangle_tree/recursive_hilbert_value.hpp"
  #include "rectangle_tree/discrete_hilbert_value.hpp"
 +#include "rectangle_tree/r_plus_tree_descent_heuristic.hpp"
 +#include "rectangle_tree/r_plus_tree_split_policy.hpp"
 +#include "rectangle_tree/minimal_coverage_sweep.hpp"
 +#include "rectangle_tree/minimal_splits_number_sweep.hpp"
 +#include "rectangle_tree/r_plus_tree_split.hpp"
 +#include "rectangle_tree/r_plus_plus_tree_auxiliary_information.hpp"
 +#include "rectangle_tree/r_plus_plus_tree_descent_heuristic.hpp"
 +#include "rectangle_tree/r_plus_plus_tree_split_policy.hpp"
  #include "rectangle_tree/typedef.hpp"
  
  #endif
diff --cc src/mlpack/core/tree/rectangle_tree/hilbert_r_tree_split_impl.hpp
index 0d4ed5f,8fff710..22f50f2
--- a/src/mlpack/core/tree/rectangle_tree/hilbert_r_tree_split_impl.hpp
+++ b/src/mlpack/core/tree/rectangle_tree/hilbert_r_tree_split_impl.hpp
@@@ -14,12 -14,11 +14,13 @@@
  namespace mlpack {
  namespace tree {
  
+ template<size_t splitOrder>
  template<typename TreeType>
- void HilbertRTreeSplit::
+ void HilbertRTreeSplit<splitOrder>::
  SplitLeafNode(TreeType* tree, std::vector<bool>& relevels)
  {
 +  if (tree->Count() <= tree->MaxLeafSize())
 +    return;
    // If we are splitting the root node, we need will do things differently so
    // that the constructor and other methods don't confuse the end user by giving
    // an address of another node.
diff --cc src/mlpack/tests/rectangle_tree_test.cpp
index 0aedb5c,4410f71..51dde78
--- a/src/mlpack/tests/rectangle_tree_test.cpp
+++ b/src/mlpack/tests/rectangle_tree_test.cpp
@@@ -771,222 -789,35 +799,249 @@@ BOOST_AUTO_TEST_CASE(DiscreteHilbertVal
    point2[1] = DBL_MAX * 0.25;
  
    BOOST_REQUIRE_EQUAL(DiscreteHilbertValue<double>::ComparePoints(point1,point2), 1);
+ 
+   arma::vec point3(4);
+   arma::vec point4(4);
+ 
+   point3[0] = -DBL_MAX;
+   point3[1] = -DBL_MAX;
+   point3[2] = -DBL_MAX;
+   point3[3] = -DBL_MAX;
+ 
+   point4[0] = 1.0;
+   point4[1] = 1.0;
+   point4[2] = 1.0;
+   point4[3] = 1.0;
+ 
+   BOOST_REQUIRE_EQUAL(DiscreteHilbertValue<double>::ComparePoints(point3,point4), -1);
+ 
+   point3[0] = -DBL_MAX;
+   point3[1] = DBL_MAX;
+   point3[2] = DBL_MAX;
+   point3[3] = DBL_MAX;
+ 
+   point4[0] = DBL_MAX;
+   point4[1] = DBL_MAX;
+   point4[2] = DBL_MAX;
+   point4[3] = DBL_MAX;
+ 
+   BOOST_REQUIRE_EQUAL(DiscreteHilbertValue<double>::ComparePoints(point3,point4), -1);
  }
  
 +template<typename TreeType>
 +void CheckOverlap(TreeType* tree)
 +{
 +  bool success = true;
 +
 +  for (size_t i = 0; i < tree->NumChildren(); i++)
 +  {
 +    success = true;
 +
 +    for (size_t j = 0; j < tree->NumChildren(); j++)
 +    {
 +      if (j == i)
 +        continue;
 +      success = false;
 +      for (size_t k = 0; k < tree->Bound().Dim(); k++)
 +      {
 +        if (tree->Children()[i]->Bound()[k].Lo() >= tree->Children()[j]->Bound()[k].Hi() ||
 +            tree->Children()[j]->Bound()[k].Lo() >= tree->Children()[i]->Bound()[k].Hi())
 +        {
 +          success = true;
 +          break;
 +        }
 +      }
 +      if (!success)
 +        break;
 +    }
 +    if (!success)
 +      break;
 +  }
 +  BOOST_REQUIRE_EQUAL(success, true);
 +
 +  for (size_t i = 0; i < tree->NumChildren(); i++)
 +    CheckOverlap(tree->Children()[i]);
 +}
 +
 +BOOST_AUTO_TEST_CASE(RPlusTreeOverlapTest)
 +{
 +  arma::mat dataset;
 +  dataset.randu(8, 1000); // 1000 points in 8 dimensions.
 +
 +  typedef RPlusTree<EuclideanDistance,
 +      NeighborSearchStat<NearestNeighborSort>,arma::mat> TreeType;
 +  TreeType rPlusTree(dataset, 20, 6, 5, 2, 0);
 +
 +  CheckOverlap(&rPlusTree);
 +}
 +
 +
 +BOOST_AUTO_TEST_CASE(RPlusTreeTraverserTest)
 +{
 +  arma::mat dataset;
 +
 +  const int numP = 1000;
 +
 +  dataset.randu(8, numP); // 1000 points in 8 dimensions.
 +  arma::Mat<size_t> neighbors1;
 +  arma::mat distances1;
 +  arma::Mat<size_t> neighbors2;
 +  arma::mat distances2;
 +
 +  typedef RPlusTree<EuclideanDistance, NeighborSearchStat<NearestNeighborSort>,
 +      arma::mat> TreeType;
 +  TreeType rPlusTree(dataset, 20, 6, 5, 2, 0);
 +
 +  // Nearest neighbor search with the X tree.
 +
 +  NeighborSearch<NearestNeighborSort, metric::LMetric<2, true>, arma::mat, RPlusTree >
 +      knn1(&rPlusTree, true);
 +
 +  BOOST_REQUIRE_EQUAL(rPlusTree.NumDescendants(), numP);
 +
 +  CheckContainment(rPlusTree);
 +  CheckExactContainment(rPlusTree);
 +  CheckHierarchy(rPlusTree);
 +  CheckOverlap(&rPlusTree);
 +
 +  knn1.Search(5, neighbors1, distances1);
 +
 +  // Nearest neighbor search the naive way.
 +  KNN knn2(dataset, true, true);
 +
 +  knn2.Search(5, neighbors2, distances2);
 +
 +  for (size_t i = 0; i < neighbors1.size(); i++)
 +  {
 +    BOOST_REQUIRE_EQUAL(neighbors1[i], neighbors2[i]);
 +    BOOST_REQUIRE_EQUAL(distances1[i], distances2[i]);
 +  }
 +}
 +
 +template<typename TreeType>
 +void CheckRPlusPlusTreeBound(const TreeType* tree)
 +{
 +  typedef bound::HRectBound<metric::EuclideanDistance,
 +      typename TreeType::ElemType> Bound;
 +
 +  bool success = true;
 +
 +  for (size_t k = 0; k < tree->Bound().Dim(); k++)
 +  {
 +    BOOST_REQUIRE_LE(tree->Bound()[k].Hi(),
 +        tree->AuxiliaryInfo().OuterBound()[k].Hi());
 +    BOOST_REQUIRE_LE(tree->AuxiliaryInfo().OuterBound()[k].Lo(),
 +        tree->Bound()[k].Lo());
 +  }
 +
 +  if (tree->IsLeaf())
 +  {
 +    for (size_t i = 0; i < tree->Count(); i++)
 +      BOOST_REQUIRE_EQUAL(true,
 +          tree->Bound().Contains(tree->Dataset().col(tree->Points()[i])));
 +
 +    return;
 +  }
 +
 +  for (size_t i = 0; i < tree->NumChildren(); i++)
 +  {
 +    const Bound& bound1 = tree->Children()[i]->AuxiliaryInfo().OuterBound();
 +    success = true;
 +
 +    for (size_t j = 0; j < tree->NumChildren(); j++)
 +    {
 +      if (j == i)
 +        continue;
 +      const Bound& bound2 = tree->Children()[j]->AuxiliaryInfo().OuterBound();
 +
 +      success = false;
 +      for (size_t k = 0; k < tree->Bound().Dim(); k++)
 +      {
 +        if (bound1[k].Lo() >= bound2[k].Hi() ||
 +            bound2[k].Lo() >= bound1[k].Hi())
 +        {
 +          success = true;
 +          break;
 +        }
 +      }
 +      if (!success)
 +        break;
 +    }
 +    if (!success)
 +      break;
 +  }
 +  BOOST_REQUIRE_EQUAL(success, true);
 +
 +  for (size_t i = 0; i < tree->NumChildren(); i++)
 +    CheckRPlusPlusTreeBound(tree->Children()[i]);
 +}
 +
 +BOOST_AUTO_TEST_CASE(RPlusPlusTreeBoundTest)
 +{
 +  arma::mat dataset;
 +  dataset.randu(8, 1000); // 1000 points in 8 dimensions.
 +
 +  typedef RPlusPlusTree<EuclideanDistance,
 +      NeighborSearchStat<NearestNeighborSort>,arma::mat> TreeType;
 +  TreeType rPlusPlusTree(dataset, 20, 6, 5, 2, 0);
 +
 +  CheckRPlusPlusTreeBound(&rPlusPlusTree);
 +
 +  typedef RectangleTree<EuclideanDistance,
 +      NeighborSearchStat<NearestNeighborSort>, arma::mat,
 +      RPlusTreeSplit<RPlusPlusTreeSplitPolicy, MinimalSplitsNumberSweep>,
 +      RPlusPlusTreeDescentHeuristic, RPlusPlusTreeAuxiliaryInformation>
 +          RPlusPlusTreeMinimalSplits;
 +
 +  RPlusPlusTreeMinimalSplits rPlusPlusTree2(dataset, 20, 6, 5, 2, 0);
 +
 +  CheckRPlusPlusTreeBound(&rPlusPlusTree2);
 +
 +}
 +
 +BOOST_AUTO_TEST_CASE(RPlusPlusTreeTraverserTest)
 +{
 +  arma::mat dataset;
 +
 +  const int numP = 1000;
 +
 +  dataset.randu(8, numP); // 1000 points in 8 dimensions.
 +  arma::Mat<size_t> neighbors1;
 +  arma::mat distances1;
 +  arma::Mat<size_t> neighbors2;
 +  arma::mat distances2;
 +
 +  typedef RPlusPlusTree<EuclideanDistance, NeighborSearchStat<NearestNeighborSort>,
 +      arma::mat> TreeType;
 +  TreeType rPlusPlusTree(dataset, 20, 6, 5, 2, 0);
 +
 +  // Nearest neighbor search with the X tree.
 +
 +  NeighborSearch<NearestNeighborSort, metric::LMetric<2, true>,
 +      arma::mat, RPlusPlusTree > knn1(&rPlusPlusTree, true);
 +
 +  BOOST_REQUIRE_EQUAL(rPlusPlusTree.NumDescendants(), numP);
 +
 +  CheckContainment(rPlusPlusTree);
 +  CheckExactContainment(rPlusPlusTree);
 +  CheckHierarchy(rPlusPlusTree);
 +  CheckRPlusPlusTreeBound(&rPlusPlusTree);
 +
 +  knn1.Search(5, neighbors1, distances1);
 +
 +  // Nearest neighbor search the naive way.
 +  KNN knn2(dataset, true, true);
 +
 +  knn2.Search(5, neighbors2, distances2);
 +
 +  for (size_t i = 0; i < neighbors1.size(); i++)
 +  {
 +    BOOST_REQUIRE_EQUAL(neighbors1[i], neighbors2[i]);
 +    BOOST_REQUIRE_EQUAL(distances1[i], distances2[i]);
 +  }
 +}
 +
 +
  // Test the tree splitting.  We set MaxLeafSize and MaxNumChildren rather low
  // to allow us to test by hand without adding hundreds of points.
  BOOST_AUTO_TEST_CASE(RTreeSplitTest)




More information about the mlpack-git mailing list