[mlpack-git] master: Merge pull request #708 from lozhnikov/vptrees (1e9f0f3)

[gitdub at mlpack.org]

Repository : https://github.com/mlpack/mlpack
On branch  : master
Link       : https://github.com/mlpack/mlpack/compare/acd81e11579f69e75aa8406b2982328c88cf1fde...1e9f0f39ea4443f0d595c395871ea8c6b27443af

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

commit 1e9f0f39ea4443f0d595c395871ea8c6b27443af
Merge: acd81e1 add74d0
Author: Ryan Curtin <ryan at ratml.org>
Date:   Mon Aug 8 14:27:29 2016 -0400

    Merge pull request #708 from lozhnikov/vptrees
    
    Vantage point tree


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

1e9f0f39ea4443f0d595c395871ea8c6b27443af
 src/mlpack/core/math/random.hpp                    |  38 ++
 src/mlpack/core/tree/CMakeLists.txt                |  13 +
 src/mlpack/core/tree/ballbound_impl.hpp            |   2 -
 src/mlpack/core/tree/binary_space_tree/traits.hpp  |   7 +
 src/mlpack/core/tree/bounds.hpp                    |   1 +
 src/mlpack/core/tree/cover_tree/traits.hpp         |   6 +
 .../tree/{ballbound.hpp => hollow_ball_bound.hpp}  | 125 +++---
 src/mlpack/core/tree/hollow_ball_bound_impl.hpp    | 380 ++++++++++++++++
 src/mlpack/core/tree/hrectbound_impl.hpp           |   2 -
 src/mlpack/core/tree/rectangle_tree/traits.hpp     |  12 +
 src/mlpack/core/tree/tree_traits.hpp               |   8 +-
 src/mlpack/core/tree/vantage_point_tree.hpp        |  21 +
 .../dual_tree_traverser.hpp                        |  34 +-
 .../dual_tree_traverser_impl.hpp                   | 237 ++++++++++
 .../single_tree_traverser.hpp                      |  18 +-
 .../single_tree_traverser_impl.hpp                 | 113 +++++
 src/mlpack/core/tree/vantage_point_tree/traits.hpp |  66 +++
 .../core/tree/vantage_point_tree/typedef.hpp       |  76 ++++
 .../vantage_point_tree/vantage_point_split.hpp     | 145 ++++++
 .../vantage_point_split_impl.hpp                   | 233 ++++++++++
 .../vantage_point_tree.hpp}                        | 217 ++++-----
 .../vantage_point_tree_impl.hpp}                   | 490 ++++++++++++---------
 src/mlpack/methods/neighbor_search/kfn_main.cpp    |  12 +-
 src/mlpack/methods/neighbor_search/knn_main.cpp    |  12 +-
 .../neighbor_search/neighbor_search_rules_impl.hpp |  53 ++-
 src/mlpack/methods/neighbor_search/ns_model.hpp    |   7 +-
 .../methods/neighbor_search/ns_model_impl.hpp      |   6 +
 .../methods/range_search/range_search_main.cpp     |  12 +-
 .../range_search/range_search_rules_impl.hpp       |  42 +-
 src/mlpack/methods/range_search/rs_model.cpp       |  21 +-
 src/mlpack/methods/range_search/rs_model.hpp       |   6 +-
 src/mlpack/methods/range_search/rs_model_impl.hpp  |  14 +
 src/mlpack/methods/rann/ra_search_impl.hpp         |   4 +-
 src/mlpack/methods/rann/ra_search_rules_impl.hpp   |  46 +-
 src/mlpack/methods/rann/ra_util.cpp                |  16 -
 src/mlpack/tests/CMakeLists.txt                    |   1 +
 src/mlpack/tests/aknn_test.cpp                     |  16 +-
 src/mlpack/tests/knn_test.cpp                      |  12 +-
 src/mlpack/tests/range_search_test.cpp             |  12 +-
 src/mlpack/tests/vantage_point_tree_test.cpp       | 337 ++++++++++++++
 40 files changed, 2401 insertions(+), 472 deletions(-)

diff --cc src/mlpack/methods/rann/ra_search_rules_impl.hpp
index 9a886db,2273940..ae13d5b
--- a/src/mlpack/methods/rann/ra_search_rules_impl.hpp
+++ b/src/mlpack/methods/rann/ra_search_rules_impl.hpp
@@@ -65,27 -68,13 +65,27 @@@ RASearchRules(const arma::mat& referenc
    Log::Info << "Minimum samples required per query: " << numSamplesReqd <<
      ", sampling ratio: " << samplingRatio << std::endl;
  
 -  if (naive) // No tree traversal; just do naive sampling here.
 +  // Let's build the list of candidate neighbors for each query point.
 +  // It will be initialized with k candidates: (WorstDistance, size_t() - 1)
 +  // The list of candidates will be updated when visiting new points with the
 +  // BaseCase() method.
 +  const Candidate def = std::make_pair(SortPolicy::WorstDistance(),
 +      size_t() - 1);
 +
 +  std::vector<Candidate> vect(k, def);
 +  CandidateList pqueue(CandidateCmp(), std::move(vect));
 +
 +  candidates.reserve(querySet.n_cols);
 +  for (size_t i = 0; i < querySet.n_cols; i++)
 +    candidates.push_back(pqueue);
 +
 +  if (naive)// No tree traversal; just do naive sampling here.
    {
      // Sample enough points.
+     arma::uvec distinctSamples;
      for (size_t i = 0; i < querySet.n_cols; ++i)
      {
-       arma::uvec distinctSamples;
-       RAUtil::ObtainDistinctSamples(numSamplesReqd, n, distinctSamples);
+       math::ObtainDistinctSamples(0, n, numSamplesReqd, distinctSamples);
        for (size_t j = 0; j < distinctSamples.n_elem; j++)
          BaseCase(i, (size_t) distinctSamples[j]);
      }