[mlpack-git] master: Merge remote-tracking branch 'upstream/master' into r_plus_tree-cherry_pick (155dbda)
gitdub at mlpack.org
gitdub at mlpack.org
Tue Jun 28 10:57:26 EDT 2016
Repository : https://github.com/mlpack/mlpack
On branch : master
Link : https://github.com/mlpack/mlpack/compare/6147ed01bab6eadcd6a5e796e259a6afacae4662...e0fd69006b17a845f066ea4de1e205fc0922739d
>---------------------------------------------------------------
commit 155dbdabbd21f2e3900e7b2b6f918052727a0bb9
Merge: 857cca0 9dd66c7
Author: Mikhail Lozhnikov <lozhnikovma at gmail.com>
Date: Tue Jun 28 17:57:26 2016 +0300
Merge remote-tracking branch 'upstream/master' into r_plus_tree-cherry_pick
>---------------------------------------------------------------
155dbdabbd21f2e3900e7b2b6f918052727a0bb9
.../tree/rectangle_tree/discrete_hilbert_value.hpp | 162 ++++++++++++---------
.../rectangle_tree/discrete_hilbert_value_impl.hpp | 146 ++++++++++---------
.../hilbert_r_tree_auxiliary_information.hpp | 56 +++----
.../hilbert_r_tree_auxiliary_information_impl.hpp | 55 +++----
.../hilbert_r_tree_descent_heuristic.hpp | 25 ++--
.../hilbert_r_tree_descent_heuristic_impl.hpp | 23 +--
.../tree/rectangle_tree/hilbert_r_tree_split.hpp | 51 ++++---
.../rectangle_tree/hilbert_r_tree_split_impl.hpp | 94 ++++++------
.../rectangle_tree/no_auxiliary_information.hpp | 23 ++-
.../r_star_tree_descent_heuristic.hpp | 14 +-
.../rectangle_tree/r_tree_descent_heuristic.hpp | 2 +-
.../x_tree_auxiliary_information.hpp | 35 +++--
src/mlpack/tests/rectangle_tree_test.cpp | 137 +++++++++--------
13 files changed, 453 insertions(+), 370 deletions(-)
diff --cc src/mlpack/core/tree/rectangle_tree/hilbert_r_tree_split_impl.hpp
index 22f50f2,1210f0d..53e8c87
--- 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
@@@ -16,11 -16,9 +16,11 @@@ namespace tree
template<size_t splitOrder>
template<typename TreeType>
- void HilbertRTreeSplit<splitOrder>::
- SplitLeafNode(TreeType* tree, std::vector<bool>& relevels)
+ 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 51dde78,58336b4..6616a83
--- a/src/mlpack/tests/rectangle_tree_test.cpp
+++ b/src/mlpack/tests/rectangle_tree_test.cpp
@@@ -825,223 -823,10 +833,224 @@@ BOOST_AUTO_TEST_CASE(DiscreteHilbertVal
point4[2] = DBL_MAX;
point4[3] = DBL_MAX;
- BOOST_REQUIRE_EQUAL(DiscreteHilbertValue<double>::ComparePoints(point3,point4), -1);
+ 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