[mlpack-git] master: Add approximate knn search tests for hybrid spill trees. (7bd4416)

[gitdub at mlpack.org]

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

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

commit 7bd4416d466904e907bcba2ecc97e7c9f5d04760
Author: MarcosPividori <marcos.pividori at gmail.com>
Date:   Sat Jul 16 12:51:21 2016 -0300

    Add approximate knn search tests for hybrid spill trees.


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

7bd4416d466904e907bcba2ecc97e7c9f5d04760
 src/mlpack/tests/aknn_test.cpp | 41 +++++++++++++++++++++++++++++++++++++++++
 1 file changed, 41 insertions(+)

diff --git a/src/mlpack/tests/aknn_test.cpp b/src/mlpack/tests/aknn_test.cpp
index f38978d..b8db91f 100644
--- a/src/mlpack/tests/aknn_test.cpp
+++ b/src/mlpack/tests/aknn_test.cpp
@@ -242,6 +242,47 @@ 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.
+ *
+ * Errors are produced if the results are not according to relative error.
+ */
+BOOST_AUTO_TEST_CASE(SingleSpillTreeTest)
+{
+  arma::mat dataset;
+  dataset.randu(50, 300); // 50 dimensional, 300 points.
+
+  const size_t k = 3;
+
+  KNN exact(dataset);
+  arma::Mat<size_t> neighborsExact;
+  arma::mat distancesExact;
+  exact.Search(dataset, k, neighborsExact, distancesExact);
+
+  double max_dist = 0;
+  for (size_t i = 0; i < neighborsExact.n_cols; ++i)
+    if (distancesExact(k - 1, i) > max_dist)
+      max_dist = distancesExact(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 satisfy the
+  // requirements on the relative error.
+  SPTree<EuclideanDistance, NeighborSearchStat<NearestNeighborSort>, arma::mat>
+      referenceTree(dataset, max_dist * 1.01 /* tau parameter */);
+
+  NeighborSearch<NearestNeighborSort, EuclideanDistance, arma::mat, SPTree>
+      spTreeSearch(&referenceTree, true, 0.05);
+
+  arma::Mat<size_t> neighborsSPTree;
+  arma::mat distancesSPTree;
+  spTreeSearch.Search(dataset, k, neighborsSPTree, distancesSPTree);
+
+  for (size_t i = 0; i < neighborsSPTree.n_elem; ++i)
+    REQUIRE_RELATIVE_ERR(distancesSPTree(i), distancesExact(i), 0.05);
+}
+
+/**
  * Make sure sparse nearest neighbors works with kd trees.
  */
 BOOST_AUTO_TEST_CASE(SparseKNNKDTreeTest)