[mlpack-git] master: Merge branch 'master' into spill-trees (d22e65a)

gitdub at mlpack.org gitdub at mlpack.org
Thu Aug 11 18:02:41 EDT 2016


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

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

commit d22e65acf2ba59ce4d2df1bb5b0a74b3ece76fee
Merge: f33a19d 067ff77
Author: MarcosPividori <marcos.pividori at gmail.com>
Date:   Thu Aug 11 19:02:41 2016 -0300

    Merge branch 'master' into spill-trees


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

d22e65acf2ba59ce4d2df1bb5b0a74b3ece76fee
 HISTORY.md                                         |   9 +-
 src/mlpack/core/dists/gamma_distribution.cpp       | 134 +++++-
 src/mlpack/core/dists/gamma_distribution.hpp       | 105 ++++-
 src/mlpack/core/math/random.hpp                    |  38 ++
 src/mlpack/core/tree/CMakeLists.txt                |  13 +
 src/mlpack/core/tree/ballbound_impl.hpp            |   2 -
 .../tree/binary_space_tree/binary_space_tree.hpp   |   3 -
 src/mlpack/core/tree/binary_space_tree/traits.hpp  |   7 +
 src/mlpack/core/tree/bounds.hpp                    |   1 +
 src/mlpack/core/tree/cosine_tree/cosine_tree.cpp   |  43 +-
 src/mlpack/core/tree/cover_tree/cover_tree.hpp     |   3 -
 .../core/tree/cover_tree/cover_tree_impl.hpp       |  32 +-
 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 -
 .../core/tree/rectangle_tree/rectangle_tree.hpp    |   3 -
 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     | 157 +++++++
 .../vantage_point_split_impl.hpp                   | 233 ++++++++++
 .../vantage_point_tree.hpp}                        | 220 +++++----
 .../vantage_point_tree_impl.hpp}                   | 503 ++++++++++++---------
 src/mlpack/methods/neighbor_search/kfn_main.cpp    |  12 +-
 src/mlpack/methods/neighbor_search/knn_main.cpp    |  12 +-
 .../neighbor_search/neighbor_search_impl.hpp       |  27 +-
 .../neighbor_search/neighbor_search_rules_impl.hpp |  53 ++-
 src/mlpack/methods/neighbor_search/ns_model.hpp    |   5 +-
 .../methods/neighbor_search/ns_model_impl.hpp      |   6 +
 src/mlpack/methods/preprocess/CMakeLists.txt       |   1 +
 .../preprocess/preprocess_describe_main.cpp        | 228 ++++++++++
 .../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/distribution_test.cpp             | 118 +++++
 src/mlpack/tests/knn_test.cpp                      |  12 +-
 src/mlpack/tests/quic_svd_test.cpp                 |  11 +-
 src/mlpack/tests/range_search_test.cpp             |  12 +-
 src/mlpack/tests/union_find_test.cpp               |  40 +-
 src/mlpack/tests/vantage_point_tree_test.cpp       | 337 ++++++++++++++
 54 files changed, 3107 insertions(+), 549 deletions(-)

diff --cc src/mlpack/methods/neighbor_search/knn_main.cpp
index 2e2d9cd,10cbd5d..32fe239
--- a/src/mlpack/methods/neighbor_search/knn_main.cpp
+++ b/src/mlpack/methods/neighbor_search/knn_main.cpp
@@@ -63,15 -63,11 +63,15 @@@ PARAM_INT_IN("k", "Number of nearest ne
  
  // The user may specify the type of tree to use, and a few parameters for tree
  // building.
- PARAM_STRING_IN("tree_type", "Type of tree to use: 'kd', 'cover', 'r', "
+ PARAM_STRING_IN("tree_type", "Type of tree to use: 'kd', 'vp', 'cover', 'r', "
 -    "'r-star', 'x', 'ball', 'hilbert-r', 'r-plus', 'r-plus-plus'.", "t", "kd");
 +    "'r-star', 'x', 'ball', 'hilbert-r', 'r-plus', 'r-plus-plus', 'spill'.",
 +    "t", "kd");
- PARAM_INT_IN("leaf_size", "Leaf size for tree building (used for kd-trees, R "
-     "trees, R* trees, X trees, Hilbert R trees, R+ trees, R++ trees, and Spill "
-     "trees).", "l", 20);
+ PARAM_INT_IN("leaf_size", "Leaf size for tree building (used for kd-trees, vp "
 -    "trees, R trees, R* trees, X trees, Hilbert R trees, R+ trees and R++ "
 -    "trees).", "l", 20);
++    "trees, R trees, R* trees, X trees, Hilbert R trees, R+ trees, R++ trees "
++    "and spill trees).", "l", 20);
 +PARAM_DOUBLE_IN("tau", "Overlapping size (for spill trees).", "u", 0);
 +PARAM_DOUBLE_IN("rho", "Balance threshold (for spill trees).", "b", 0.7);
 +
  PARAM_FLAG("random_basis", "Before tree-building, project the data onto a "
      "random orthogonal basis.", "R");
  PARAM_INT_IN("seed", "Random seed (if 0, std::time(NULL) is used).", "s", 0);
@@@ -211,12 -180,12 +211,14 @@@ int main(int argc, char *argv[]
        tree = KNNModel::R_PLUS_TREE;
      else if (treeType == "r-plus-plus")
        tree = KNNModel::R_PLUS_PLUS_TREE;
 +    else if (treeType == "spill")
 +      tree = KNNModel::SPILL_TREE;
+     else if (treeType == "vp")
+       tree = KNNModel::VP_TREE;
      else
        Log::Fatal << "Unknown tree type '" << treeType << "'; valid choices are "
            << "'kd', 'cover', 'r', 'r-star', 'x', 'ball', 'hilbert-r', "
-           << "'r-plus', 'r-plus-plus' and 'spill'." << endl;
 -          << "'r-plus', 'r-plus-plus' and 'vp'." << endl;
++          << "'r-plus', 'r-plus-plus', 'vp' and 'spill'." << endl;
  
      knn.TreeType() = tree;
      knn.RandomBasis() = randomBasis;
diff --cc src/mlpack/methods/neighbor_search/neighbor_search_impl.hpp
index da3b28e,d5112cb..cbc89ff
--- a/src/mlpack/methods/neighbor_search/neighbor_search_impl.hpp
+++ b/src/mlpack/methods/neighbor_search/neighbor_search_impl.hpp
@@@ -550,11 -553,11 +554,14 @@@ Search(Tree* queryTree
    scores += rules.Scores();
    baseCases += rules.BaseCases();
  
+   Log::Info << rules.Scores() << " node combinations were scored." << std::endl;
+   Log::Info << rules.BaseCases() << " base cases were calculated." << std::endl;
+ 
    rules.GetResults(*neighborPtr, distances);
  
 +  Log::Info << rules.Scores() << " node combinations were scored.\n";
 +  Log::Info << rules.BaseCases() << " base cases were calculated.\n";
 +
    Timer::Stop("computing_neighbors");
  
    // Do we need to map indices?
diff --cc src/mlpack/methods/neighbor_search/ns_model.hpp
index 4f34e07,fc782fe..2162903
--- a/src/mlpack/methods/neighbor_search/ns_model.hpp
+++ b/src/mlpack/methods/neighbor_search/ns_model.hpp
@@@ -13,10 -13,9 +13,11 @@@
  #include <mlpack/core/tree/binary_space_tree.hpp>
  #include <mlpack/core/tree/cover_tree.hpp>
  #include <mlpack/core/tree/rectangle_tree.hpp>
 +#include <mlpack/core/tree/spill_tree.hpp>
+ #include <mlpack/core/tree/vantage_point_tree.hpp>
  #include <boost/variant.hpp>
  #include "neighbor_search.hpp"
 +#include "spill_search.hpp"
  
  namespace mlpack {
  namespace neighbor {
@@@ -283,7 -258,7 +284,8 @@@ class NSMode
      HILBERT_R_TREE,
      R_PLUS_TREE,
      R_PLUS_PLUS_TREE,
-     SPILL_TREE
++    SPILL_TREE,
+     VP_TREE
    };
  
   private:
@@@ -317,7 -287,7 +319,8 @@@
                   NSType<SortPolicy, tree::HilbertRTree>*,
                   NSType<SortPolicy, tree::RPlusTree>*,
                   NSType<SortPolicy, tree::RPlusPlusTree>*,
 -                 NSType<SortPolicy, tree::VPTree>*> nSearch;
++                 NSType<SortPolicy, tree::VPTree>*,
 +                 NSSpillType*> nSearch;
  
   public:
    /**
diff --cc src/mlpack/methods/neighbor_search/ns_model_impl.hpp
index 29cc167,2ca8be5..07c6f21
--- a/src/mlpack/methods/neighbor_search/ns_model_impl.hpp
+++ b/src/mlpack/methods/neighbor_search/ns_model_impl.hpp
@@@ -459,12 -394,13 +459,16 @@@ void NSModel<SortPolicy>::BuildModel(ar
        nSearch = new NSType<SortPolicy, tree::RPlusPlusTree>(naive, singleMode,
            epsilon);
        break;
+     case VP_TREE:
+       nSearch = new NSType<SortPolicy, tree::VPTree>(naive, singleMode,
+           epsilon);
+       break;
 +    case SPILL_TREE:
 +      nSearch = new NSSpillType(naive, singleMode, tau, leafSize, rho, epsilon);
 +      break;
    }
  
 -  TrainVisitor<SortPolicy> tn(std::move(referenceSet), leafSize);
 +  TrainVisitor<SortPolicy> tn(std::move(referenceSet), leafSize, tau, rho);
    boost::apply_visitor(tn, nSearch);
  
    if (!naive)
@@@ -546,8 -482,8 +550,10 @@@ std::string NSModel<SortPolicy>::TreeNa
        return "R+ tree";
      case R_PLUS_PLUS_TREE:
        return "R++ tree";
 +    case SPILL_TREE:
 +      return "Spill tree";
+     case VP_TREE:
+       return "Vantage point tree";
      default:
        return "unknown tree";
    }
diff --cc src/mlpack/tests/CMakeLists.txt
index a4b7420,4beb2e1..ecd2d58
--- a/src/mlpack/tests/CMakeLists.txt
+++ b/src/mlpack/tests/CMakeLists.txt
@@@ -85,6 -79,11 +85,7 @@@ add_executable(mlpack_tes
    tree_test.cpp
    tree_traits_test.cpp
    union_find_test.cpp
 -  svd_batch_test.cpp
 -  svd_incremental_test.cpp
 -  nystroem_method_test.cpp
 -  armadillo_svd_test.cpp
+   vantage_point_tree_test.cpp
  )
  # Link dependencies of test executable.
  target_link_libraries(mlpack_test




More information about the mlpack-git mailing list