[mlpack-git] master: Add exact knn search tests for hybrid spill trees. (946eddf)

[gitdub at mlpack.org]

Repository : https://github.com/mlpack/mlpack
On branch  : master
Link       : https://github.com/mlpack/mlpack/compare/0f4b25acd6aaa14294c044874ba6cc0751712baa...0a19d07bd39e6223991976474bc79671ba8aa0f0

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

commit 946eddfb4f382ca3fa08b57d4aafab033e36feb8
Author: MarcosPividori <marcos.pividori at gmail.com>
Date:   Sat Jul 16 12:52:27 2016 -0300

    Add exact knn search tests for hybrid spill trees.


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

946eddfb4f382ca3fa08b57d4aafab033e36feb8
 src/mlpack/tests/knn_test.cpp | 43 +++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 43 insertions(+)

diff --git a/src/mlpack/tests/knn_test.cpp b/src/mlpack/tests/knn_test.cpp
index 0de22b8..c82fffd 100644
--- a/src/mlpack/tests/knn_test.cpp
+++ b/src/mlpack/tests/knn_test.cpp
@@ -889,6 +889,49 @@ BOOST_AUTO_TEST_CASE(DualBallTreeTest)
 }
 
 /**
+ * Test the spill tree hybrid sp-tree search (defeatist search on overlapping
+ * nodes, and backtracking in non-overlapping nodes) against the naive method.
+ * This uses only a random reference dataset.
+ */
+BOOST_AUTO_TEST_CASE(SingleSpillTreeTest)
+{
+  arma::mat dataset;
+  dataset.randu(50, 300); // 50 dimensional, 300 points.
+
+  const size_t k = 3;
+
+  KNN naive(dataset);
+  arma::Mat<size_t> neighborsNaive;
+  arma::mat distancesNaive;
+  naive.Search(dataset, k, neighborsNaive, distancesNaive);
+
+  double max_dist = 0;
+  for (size_t i = 0; i < neighborsNaive.n_cols; ++i)
+    if (distancesNaive(k - 1, i) > max_dist)
+      max_dist = distancesNaive(k - 1, i);
+
+  // If we are sure that tau is a valid upper bound of the kth nearest neighbor
+  // of the query points, then we can be sure that we will get an exact
+  // solution.
+  SPTree<EuclideanDistance, NeighborSearchStat<NearestNeighborSort>, arma::mat>
+      referenceTree(dataset, max_dist * 1.01 /* tau parameter */);
+
+  NeighborSearch<NearestNeighborSort, EuclideanDistance, arma::mat, SPTree>
+      spTreeSearch(&referenceTree, true);
+
+  arma::Mat<size_t> neighborsSPTree;
+  arma::mat distancesSPTree;
+  spTreeSearch.Search(dataset, k, neighborsSPTree, distancesSPTree);
+
+  for (size_t i = 0; i < neighborsSPTree.n_elem; ++i)
+  {
+    BOOST_REQUIRE_EQUAL(neighborsSPTree(i), neighborsNaive(i));
+    BOOST_REQUIRE_CLOSE(distancesSPTree(i), distancesNaive(i), 1e-5);
+  }
+}
+
+
+/**
  * Make sure sparse nearest neighbors works with kd trees.
  */
 BOOST_AUTO_TEST_CASE(SparseKNNKDTreeTest)