[mlpack-git] master: Merge remote-tracking branch 'upstream/master' into r-proj-tree (079cb80)

gitdub at mlpack.org gitdub at mlpack.org
Fri Aug 12 15:45:28 EDT 2016


Repository : https://github.com/mlpack/mlpack
On branch  : master
Link       : https://github.com/mlpack/mlpack/compare/a7794bde8082c691553152393e1e230098f5e920...87776e52cf9ead63fa458118a0cfd2fe46b23466

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

commit 079cb8034411ac11639d3d129cdaaf919e701a23
Merge: dc0b456 067ff77
Author: Mikhail Lozhnikov <lozhnikovma at gmail.com>
Date:   Fri Aug 12 22:45:28 2016 +0300

    Merge remote-tracking branch 'upstream/master' into r-proj-tree


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

079cb8034411ac11639d3d129cdaaf919e701a23
 HISTORY.md                                         |   3 +
 src/mlpack/core/dists/gamma_distribution.cpp       |  91 +++
 src/mlpack/core/dists/gamma_distribution.hpp       |  91 ++-
 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  |  19 +
 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 -
 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}                        | 256 ++++-----
 .../vantage_point_tree_impl.hpp}                   | 623 ++++++++++-----------
 src/mlpack/methods/neighbor_search/kfn_main.cpp    |  13 +-
 src/mlpack/methods/neighbor_search/knn_main.cpp    |  13 +-
 .../neighbor_search/neighbor_search_impl.hpp       |  27 +-
 .../neighbor_search/neighbor_search_rules_impl.hpp |  53 +-
 src/mlpack/methods/neighbor_search/ns_model.hpp    |   3 +
 .../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     |  14 +-
 .../range_search/range_search_rules_impl.hpp       |  42 +-
 src/mlpack/methods/range_search/rs_model.cpp       |  19 +
 src/mlpack/methods/range_search/rs_model.hpp       |   4 +
 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                     |  28 +-
 src/mlpack/tests/distribution_test.cpp             |  96 ++++
 src/mlpack/tests/knn_test.cpp                      |  28 +-
 src/mlpack/tests/quic_svd_test.cpp                 |  11 +-
 src/mlpack/tests/range_search_test.cpp             |  28 +-
 src/mlpack/tests/vantage_point_tree_test.cpp       | 337 +++++++++++
 52 files changed, 3011 insertions(+), 698 deletions(-)

diff --cc src/mlpack/core/tree/binary_space_tree/traits.hpp
index 15cadc1,611447f..198cb10
--- a/src/mlpack/core/tree/binary_space_tree/traits.hpp
+++ b/src/mlpack/core/tree/binary_space_tree/traits.hpp
@@@ -42,89 -42,12 +42,107 @@@ class TreeTraits<BinarySpaceTree<Metric
    static const bool FirstPointIsCentroid = false;
  
    /**
+    * There is no guarantee that the first point of the first sibling is the
+    * centroid of other siblings.
+    */
+   static const bool FirstSiblingFirstPointIsCentroid = false;
+ 
+   /**
 +   * The tree has not got duplicated points.
 +   */
 +  static const bool HasDuplicatedPoints = false;
 +
 +  /**
 +   * Points are not contained at multiple levels of the binary space tree.
 +   */
 +  static const bool HasSelfChildren = false;
 +
 +  /**
 +   * Points are rearranged during building of the tree.
 +   */
 +  static const bool RearrangesDataset = true;
 +
 +  /**
 +   * This is always a binary tree.
 +   */
 +  static const bool BinaryTree = true;
 +};
 +
 +template<typename MetricType,
 +         typename StatisticType,
 +         typename MatType,
 +         template<typename BoundMetricType, typename...> class BoundType>
 +class TreeTraits<BinarySpaceTree<MetricType, StatisticType, MatType, BoundType,
 +                                 RPTreeMaxSplit>>
 +{
 + public:
 +  /**
 +   * Children of a random projection tree node may overlap.
 +   */
 +  static const bool HasOverlappingChildren = true;
 +
 +  /**
 +   * The tree has not got duplicated points.
 +   */
 +  static const bool HasDuplicatedPoints = false;
 +
 +  /**
 +   * There is no guarantee that the first point in a node is its centroid.
 +   */
 +  static const bool FirstPointIsCentroid = false;
 +
 +  /**
++   * There is no guarantee that the first point of the first sibling is the
++   * centroid of other siblings.
++   */
++  static const bool FirstSiblingFirstPointIsCentroid = false;
++
++  /**
 +   * Points are not contained at multiple levels of the binary space tree.
 +   */
 +  static const bool HasSelfChildren = false;
 +
 +  /**
 +   * Points are rearranged during building of the tree.
 +   */
 +  static const bool RearrangesDataset = true;
 +
 +  /**
 +   * This is always a binary tree.
 +   */
 +  static const bool BinaryTree = true;
 +};
 +
 +template<typename MetricType,
 +         typename StatisticType,
 +         typename MatType,
 +         template<typename BoundMetricType, typename...> class BoundType>
 +class TreeTraits<BinarySpaceTree<MetricType, StatisticType, MatType, BoundType,
 +                                 RPTreeMeanSplit>>
 +{
 + public:
 +  /**
 +   * Children of a random projection tree node may overlap.
 +   */
 +  static const bool HasOverlappingChildren = true;
 +
 +  /**
 +   * The tree has not got duplicated points.
 +   */
 +  static const bool HasDuplicatedPoints = false;
 +
 +  /**
 +   * There is no guarantee that the first point in a node is its centroid.
 +   */
 +  static const bool FirstPointIsCentroid = false;
 +
 +  /**
++   * There is no guarantee that the first point of the first sibling is the
++   * centroid of other siblings.
++   */
++  static const bool FirstSiblingFirstPointIsCentroid = false;
++
++  /**
     * Points are not contained at multiple levels of the binary space tree.
     */
    static const bool HasSelfChildren = false;
diff --cc src/mlpack/methods/neighbor_search/kfn_main.cpp
index 16e58a4,b223d7c..34bc6ee
--- a/src/mlpack/methods/neighbor_search/kfn_main.cpp
+++ b/src/mlpack/methods/neighbor_search/kfn_main.cpp
@@@ -61,12 -61,11 +61,12 @@@ PARAM_INT_IN("k", "Number of furthest n
  
  // The user may specify the type of tree to use, and a few pararmeters for tree
  // building.
- PARAM_STRING_IN("tree_type", "Type of tree to use: 'kd', 'rp-tree', "
 -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");
 -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);
++PARAM_STRING_IN("tree_type", "Type of tree to use: 'kd', 'vp', 'rp-tree', "
 +    "'max-split-rp-tree', 'cover', 'r', 'r-star', 'x', 'ball', 'hilbert-r', "
 +    "'r-plus', 'r-plus-plus'.", "t", "kd");
 +PARAM_INT_IN("leaf_size", "Leaf size for tree building (used for kd-trees, "
-     "random projection trees, R trees, R* trees, X trees, Hilbert R trees, "
-     "R+ trees and R++ trees).", "l", 20);
++    "vp trees, random projection trees, R trees, R* trees, X trees, "
++    "Hilbert R trees, R+ trees and R++ trees).", "l", 20);
  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);
@@@ -195,14 -194,12 +195,17 @@@ int main(int argc, char *argv[]
        tree = KFNModel::R_PLUS_TREE;
      else if (treeType == "r-plus-plus")
        tree = KFNModel::R_PLUS_PLUS_TREE;
+     else if (treeType == "vp")
+       tree = KFNModel::VP_TREE;
 +    else if (treeType == "rp-tree")
 +      tree = KFNModel::RP_TREE;
 +    else if (treeType == "max-split-rp-tree")
 +      tree = KFNModel::MAX_SPLIT_RP_TREE;
      else
        Log::Fatal << "Unknown tree type '" << treeType << "'; valid choices are "
-           << "'kd', 'rp-tree', 'max-split-rp-tree', 'cover', 'r', 'r-star', "
-           << "'x', 'ball', 'hilbert-r', 'r-plus' and 'r-plus-plus'." << endl;
 -          << "'kd', 'cover', 'r', 'r-star', 'x', 'ball', 'hilbert-r', "
 -          << "'r-plus', 'r-plus-plus' and 'vp'." << endl;
++          << "'kd', 'vp', 'rp-tree', 'max-split-rp-tree', 'cover', 'r', "
++          << "'r-star', 'x', 'ball', 'hilbert-r', 'r-plus' and 'r-plus-plus'."
++          << endl;
  
      kfn.TreeType() = tree;
      kfn.RandomBasis() = randomBasis;
diff --cc src/mlpack/methods/neighbor_search/knn_main.cpp
index 2f3a713,10cbd5d..5fa4c88
--- a/src/mlpack/methods/neighbor_search/knn_main.cpp
+++ b/src/mlpack/methods/neighbor_search/knn_main.cpp
@@@ -63,12 -63,11 +63,12 @@@ 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', 'rp-tree', "
 -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");
 -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);
++PARAM_STRING_IN("tree_type", "Type of tree to use: 'kd', 'vp', 'rp-tree', "
 +    "'max-split-rp-tree', 'cover', 'r', 'r-star', 'x', 'ball', 'hilbert-r', "
 +    "'r-plus', 'r-plus-plus'.", "t", "kd");
 +PARAM_INT_IN("leaf_size", "Leaf size for tree building (used for kd-trees, "
-     "random projection trees, R trees, R* trees, X trees, Hilbert R trees, "
-     "R+ trees and R++ trees).", "l", 20);
++    "vp trees, random projection trees, R trees, R* trees, X trees, "
++    "Hilbert R trees, R+ trees and R++ trees).", "l", 20);
  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);
@@@ -181,14 -180,12 +181,17 @@@ 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 == "vp")
+       tree = KNNModel::VP_TREE;
 +    else if (treeType == "rp-tree")
 +      tree = KNNModel::RP_TREE;
 +    else if (treeType == "max-split-rp-tree")
 +      tree = KNNModel::MAX_SPLIT_RP_TREE;
      else
        Log::Fatal << "Unknown tree type '" << treeType << "'; valid choices are "
-           << "'kd', 'rp-tree', 'max-split-rp-tree', 'cover', 'r', 'r-star', "
-           << "'x', 'ball', 'hilbert-r', 'r-plus' and 'r-plus-plus'." << endl;
 -          << "'kd', 'cover', 'r', 'r-star', 'x', 'ball', 'hilbert-r', "
 -          << "'r-plus', 'r-plus-plus' and 'vp'." << endl;
++          << "'kd', 'vp', 'rp-tree', 'max-split-rp-tree', 'cover', 'r', "
++          << "'r-star', 'x', 'ball', 'hilbert-r', 'r-plus' and 'r-plus-plus'."
++          << endl;
  
      knn.TreeType() = tree;
      knn.RandomBasis() = randomBasis;
diff --cc src/mlpack/methods/neighbor_search/ns_model.hpp
index f2e2fbd,fc782fe..8cf3bd7
--- a/src/mlpack/methods/neighbor_search/ns_model.hpp
+++ b/src/mlpack/methods/neighbor_search/ns_model.hpp
@@@ -257,8 -258,7 +258,9 @@@ class NSMode
      HILBERT_R_TREE,
      R_PLUS_TREE,
      R_PLUS_PLUS_TREE,
 -    VP_TREE
++    VP_TREE,
 +    RP_TREE,
 +    MAX_SPLIT_RP_TREE
    };
  
   private:
@@@ -287,8 -287,7 +289,9 @@@
                   NSType<SortPolicy, tree::HilbertRTree>*,
                   NSType<SortPolicy, tree::RPlusTree>*,
                   NSType<SortPolicy, tree::RPlusPlusTree>*,
 -                 NSType<SortPolicy, tree::VPTree>*> nSearch;
++                 NSType<SortPolicy, tree::VPTree>*,
 +                 NSType<SortPolicy, tree::RPTree>*,
 +                 NSType<SortPolicy, tree::MaxSplitRPTree>*> nSearch;
  
   public:
    /**
diff --cc src/mlpack/methods/neighbor_search/ns_model_impl.hpp
index d6ff6cc,2ca8be5..d026cd1
--- a/src/mlpack/methods/neighbor_search/ns_model_impl.hpp
+++ b/src/mlpack/methods/neighbor_search/ns_model_impl.hpp
@@@ -394,14 -394,10 +394,18 @@@ 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 RP_TREE:
 +      nSearch = new NSType<SortPolicy, tree::RPTree>(naive, singleMode,
 +          epsilon);
 +      break;
 +    case MAX_SPLIT_RP_TREE:
 +      nSearch = new NSType<SortPolicy, tree::MaxSplitRPTree>(naive, singleMode,
 +          epsilon);
 +      break;
    }
  
    TrainVisitor<SortPolicy> tn(std::move(referenceSet), leafSize);
@@@ -486,10 -482,8 +490,12 @@@ std::string NSModel<SortPolicy>::TreeNa
        return "R+ tree";
      case R_PLUS_PLUS_TREE:
        return "R++ tree";
+     case VP_TREE:
+       return "Vantage point tree";
 +    case RP_TREE:
 +      return "Random projection tree (mean split)";
 +    case MAX_SPLIT_RP_TREE:
 +      return "Random projection tree (max split)";
      default:
        return "unknown tree";
    }
diff --cc src/mlpack/methods/range_search/range_search_main.cpp
index d014bc4,27813c0..ed79aa2
--- a/src/mlpack/methods/range_search/range_search_main.cpp
+++ b/src/mlpack/methods/range_search/range_search_main.cpp
@@@ -70,13 -70,11 +70,12 @@@ PARAM_DOUBLE_IN("min", "Lower bound in 
  
  // 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', 'rp-tree', "
 -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");
 -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);
++PARAM_STRING_IN("tree_type", "Type of tree to use: 'kd', 'vp', 'rp-tree', "
 +    "'max-split-rp-tree', 'cover', 'r', 'r-star', 'x', 'ball', 'hilbert-r', "
 +    "'r-plus', 'r-plus-plus'.", "t", "kd");
 +PARAM_INT_IN("leaf_size", "Leaf size for tree building (used for kd-trees, "
-     "random projection trees, R trees, R* trees, X trees, Hilbert R trees, "
-     "R+ trees and R++ trees).", "l",
-     20);
++    "vp trees, random projection trees, R trees, R* trees, X trees, "
++    "Hilbert R trees, R+ trees and R++ trees).", "l", 20);
  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);
@@@ -184,14 -182,12 +183,17 @@@ int main(int argc, char *argv[]
        tree = RSModel::R_PLUS_TREE;
      else if (treeType == "r-plus-plus")
        tree = RSModel::R_PLUS_PLUS_TREE;
+     else if (treeType == "vp")
+       tree = RSModel::VP_TREE;
 +    else if (treeType == "rp-tree")
 +      tree = RSModel::RP_TREE;
 +    else if (treeType == "max-split-rp-tree")
 +      tree = RSModel::MAX_SPLIT_RP_TREE;
      else
        Log::Fatal << "Unknown tree type '" << treeType << "; valid choices are "
-           << "'kd', 'rp-tree-max', 'rp-tree-mean', 'cover', 'r', 'r-star', "
-           << "'x', 'ball', 'hilbert-r', 'r-plus' and 'r-plus-plus'." << endl;
 -          << "'kd', 'cover', 'r', 'r-star', 'x', 'ball', 'hilbert-r', "
 -          << "'r-plus', 'r-plus-plus' and 'vp'." << endl;
++          << "'kd', 'vp', 'rp-tree-max', 'rp-tree-mean', 'cover', 'r', "
++          << "'r-star', 'x', 'ball', 'hilbert-r', 'r-plus' and 'r-plus-plus'."
++          << endl;
  
      rs.TreeType() = tree;
      rs.RandomBasis() = randomBasis;
diff --cc src/mlpack/methods/range_search/rs_model.cpp
index e3d5a8e,10514c6..d5d03f4
--- a/src/mlpack/methods/range_search/rs_model.cpp
+++ b/src/mlpack/methods/range_search/rs_model.cpp
@@@ -26,8 -26,7 +26,9 @@@ RSModel::RSModel(TreeTypes treeType, bo
      hilbertRTreeRS(NULL),
      rPlusTreeRS(NULL),
      rPlusPlusTreeRS(NULL),
 -    vpTreeRS(NULL)
++    vpTreeRS(NULL),
 +    rpTreeRS(NULL),
 +    maxSplitPRTreeRS(NULL)
  {
    // Nothing to do.
  }
@@@ -139,19 -138,14 +140,24 @@@ void RSModel::BuildModel(arma::mat&& re
        break;
  
      case R_PLUS_PLUS_TREE:
 -      rPlusPlusTreeRS = new RSType<tree::RPlusPlusTree>(move(referenceSet), naive,
 -          singleMode);
 +      rPlusPlusTreeRS = new RSType<tree::RPlusPlusTree>(move(referenceSet),
 +          naive, singleMode);
        break;
  
+     case VP_TREE:
+       vpTreeRS = new RSType<tree::VPTree>(move(referenceSet), naive,
+           singleMode);
+       break;
++
 +    case RP_TREE:
 +      rpTreeRS = new RSType<tree::RPTree>(move(referenceSet), naive,
 +          singleMode);
 +      break;
 +
 +    case MAX_SPLIT_RP_TREE:
 +      maxSplitPRTreeRS = new RSType<tree::MaxSplitRPTree>(move(referenceSet),
 +          naive, singleMode);
 +      break;
    }
  
    if (!naive)
@@@ -274,13 -268,9 +280,17 @@@ void RSModel::Search(arma::mat&& queryS
        rPlusPlusTreeRS->Search(querySet, range, neighbors, distances);
        break;
  
+     case VP_TREE:
+       vpTreeRS->Search(querySet, range, neighbors, distances);
+       break;
++
 +    case RP_TREE:
 +      rpTreeRS->Search(querySet, range, neighbors, distances);
 +      break;
 +
 +    case MAX_SPLIT_RP_TREE:
 +      maxSplitPRTreeRS->Search(querySet, range, neighbors, distances);
 +      break;
    }
  }
  
@@@ -336,13 -326,9 +346,17 @@@ void RSModel::Search(const math::Range
        rPlusPlusTreeRS->Search(range, neighbors, distances);
        break;
  
+     case VP_TREE:
+       vpTreeRS->Search(range, neighbors, distances);
+       break;
++
 +    case RP_TREE:
 +      rpTreeRS->Search(range, neighbors, distances);
 +      break;
 +
 +    case MAX_SPLIT_RP_TREE:
 +      maxSplitPRTreeRS->Search(range, neighbors, distances);
 +      break;
    }
  }
  
@@@ -369,10 -355,8 +383,12 @@@ std::string RSModel::TreeName() cons
        return "R+ tree";
      case R_PLUS_PLUS_TREE:
        return "R++ tree";
+     case VP_TREE:
+       return "Vantage point tree";
 +    case RP_TREE:
 +      return "Random projection tree (mean split)";
 +    case MAX_SPLIT_RP_TREE:
 +      return "Random projection tree (max split)";
      default:
        return "unknown tree";
    }
@@@ -399,10 -383,8 +415,12 @@@ void RSModel::CleanMemory(
      delete rPlusTreeRS;
    if (rPlusPlusTreeRS)
      delete rPlusPlusTreeRS;
+   if (vpTreeRS)
+     delete vpTreeRS;
 +  if (rpTreeRS)
 +    delete rpTreeRS;
 +  if (maxSplitPRTreeRS)
 +    delete maxSplitPRTreeRS;
  
    kdTreeRS = NULL;
    coverTreeRS = NULL;
@@@ -413,6 -395,5 +431,7 @@@
    hilbertRTreeRS = NULL;
    rPlusTreeRS = NULL;
    rPlusPlusTreeRS = NULL;
+   vpTreeRS = NULL;
 +  rpTreeRS = NULL;
 +  maxSplitPRTreeRS = NULL;
  }
diff --cc src/mlpack/methods/range_search/rs_model.hpp
index e5c5335,8c7af3b..6a73c85
--- a/src/mlpack/methods/range_search/rs_model.hpp
+++ b/src/mlpack/methods/range_search/rs_model.hpp
@@@ -33,8 -34,7 +34,9 @@@ class RSMode
      HILBERT_R_TREE,
      R_PLUS_TREE,
      R_PLUS_PLUS_TREE,
 -    VP_TREE
++    VP_TREE,
 +    RP_TREE,
 +    MAX_SPLIT_RP_TREE
    };
  
   private:
@@@ -71,12 -71,8 +73,14 @@@
    RSType<tree::RPlusTree>* rPlusTreeRS;
    //! R++ tree based range search object (NULL if not in use).
    RSType<tree::RPlusPlusTree>* rPlusPlusTreeRS;
+   //! VP tree based range search object (NULL if not in use).
+   RSType<tree::VPTree>* vpTreeRS;
 +  //! Random projection tree (mean) based range search object
 +  //! (NULL if not in use).
 +  RSType<tree::RPTree>* rpTreeRS;
 +  //! Random projection tree (max) based range search object
 +  //! (NULL if not in use).
 +  RSType<tree::MaxSplitRPTree>* maxSplitPRTreeRS;
  
   public:
    /**
diff --cc src/mlpack/methods/range_search/rs_model_impl.hpp
index 5f67d17,fbc6580..8ad93fe
--- a/src/mlpack/methods/range_search/rs_model_impl.hpp
+++ b/src/mlpack/methods/range_search/rs_model_impl.hpp
@@@ -66,13 -66,9 +66,17 @@@ void RSModel::Serialize(Archive& ar, co
        ar & CreateNVP(rPlusPlusTreeRS, "range_search_model");
        break;
  
+     case VP_TREE:
+       ar & CreateNVP(vpTreeRS, "range_search_model");
+       break;
++
 +    case RP_TREE:
 +      ar & CreateNVP(rpTreeRS, "range_search_model");
 +      break;
 +
 +    case MAX_SPLIT_RP_TREE:
 +      ar & CreateNVP(maxSplitPRTreeRS, "range_search_model");
 +      break;
    }
  }
  
@@@ -96,10 -92,8 +100,12 @@@ inline const arma::mat& RSModel::Datase
      return rPlusTreeRS->ReferenceSet();
    else if (rPlusPlusTreeRS)
      return rPlusPlusTreeRS->ReferenceSet();
+   else if (vpTreeRS)
+     return vpTreeRS->ReferenceSet();
 +  else if (rpTreeRS)
 +    return rpTreeRS->ReferenceSet();
 +  else if (maxSplitPRTreeRS)
 +    return maxSplitPRTreeRS->ReferenceSet();
  
    throw std::runtime_error("no range search model initialized");
  }
@@@ -124,10 -118,8 +130,12 @@@ inline bool RSModel::SingleMode() cons
      return rPlusTreeRS->SingleMode();
    else if (rPlusPlusTreeRS)
      return rPlusPlusTreeRS->SingleMode();
+   else if (vpTreeRS)
+     return vpTreeRS->SingleMode();
 +  else if (rpTreeRS)
 +    return rpTreeRS->SingleMode();
 +  else if (maxSplitPRTreeRS)
 +    return maxSplitPRTreeRS->SingleMode();
  
    throw std::runtime_error("no range search model initialized");
  }
@@@ -152,10 -144,8 +160,12 @@@ inline bool& RSModel::SingleMode(
      return rPlusTreeRS->SingleMode();
    else if (rPlusPlusTreeRS)
      return rPlusPlusTreeRS->SingleMode();
+   else if (vpTreeRS)
+     return vpTreeRS->SingleMode();
 +  else if (rpTreeRS)
 +    return rpTreeRS->SingleMode();
 +  else if (maxSplitPRTreeRS)
 +    return maxSplitPRTreeRS->SingleMode();
  
    throw std::runtime_error("no range search model initialized");
  }
@@@ -180,10 -170,8 +190,12 @@@ inline bool RSModel::Naive() cons
      return rPlusTreeRS->Naive();
    else if (rPlusPlusTreeRS)
      return rPlusPlusTreeRS->Naive();
+   else if (vpTreeRS)
+     return vpTreeRS->Naive();
 +  else if (rpTreeRS)
 +    return rpTreeRS->Naive();
 +  else if (maxSplitPRTreeRS)
 +    return maxSplitPRTreeRS->Naive();
  
    throw std::runtime_error("no range search model initialized");
  }
@@@ -208,10 -196,8 +220,12 @@@ inline bool& RSModel::Naive(
      return rPlusTreeRS->Naive();
    else if (rPlusPlusTreeRS)
      return rPlusPlusTreeRS->Naive();
+   else if (vpTreeRS)
+     return vpTreeRS->Naive();
 +  else if (rpTreeRS)
 +    return rpTreeRS->Naive();
 +  else if (maxSplitPRTreeRS)
 +    return maxSplitPRTreeRS->Naive();
  
    throw std::runtime_error("no range search model initialized");
  }
diff --cc src/mlpack/tests/aknn_test.cpp
index 8da2476,98466b4..8fbcaa8
--- a/src/mlpack/tests/aknn_test.cpp
+++ b/src/mlpack/tests/aknn_test.cpp
@@@ -287,7 -287,7 +287,7 @@@ BOOST_AUTO_TEST_CASE(KNNModelTest
    arma::mat referenceData = arma::randu<arma::mat>(10, 200);
  
    // Build all the possible models.
-   KNNModel models[22];
 -  KNNModel models[20];
++  KNNModel models[24];
    models[0] = KNNModel(KNNModel::TreeTypes::KD_TREE, true);
    models[1] = KNNModel(KNNModel::TreeTypes::KD_TREE, false);
    models[2] = KNNModel(KNNModel::TreeTypes::COVER_TREE, true);
@@@ -306,10 -306,8 +306,12 @@@
    models[15] = KNNModel(KNNModel::TreeTypes::R_PLUS_TREE, false);
    models[16] = KNNModel(KNNModel::TreeTypes::R_PLUS_PLUS_TREE, true);
    models[17] = KNNModel(KNNModel::TreeTypes::R_PLUS_PLUS_TREE, false);
-   models[18] = KNNModel(KNNModel::TreeTypes::RP_TREE, true);
-   models[19] = KNNModel(KNNModel::TreeTypes::RP_TREE, false);
-   models[20] = KNNModel(KNNModel::TreeTypes::MAX_SPLIT_RP_TREE, true);
-   models[21] = KNNModel(KNNModel::TreeTypes::MAX_SPLIT_RP_TREE, false);
+   models[18] = KNNModel(KNNModel::TreeTypes::VP_TREE, true);
+   models[19] = KNNModel(KNNModel::TreeTypes::VP_TREE, false);
++  models[20] = KNNModel(KNNModel::TreeTypes::RP_TREE, true);
++  models[21] = KNNModel(KNNModel::TreeTypes::RP_TREE, false);
++  models[22] = KNNModel(KNNModel::TreeTypes::MAX_SPLIT_RP_TREE, true);
++  models[23] = KNNModel(KNNModel::TreeTypes::MAX_SPLIT_RP_TREE, false);
  
    for (size_t j = 0; j < 3; ++j)
    {
@@@ -319,7 -317,7 +321,7 @@@
      arma::mat distancesExact;
      aknn.Search(queryData, 3, neighborsExact, distancesExact);
  
-     for (size_t i = 0; i < 22; ++i)
 -    for (size_t i = 0; i < 20; ++i)
++    for (size_t i = 0; i < 24; ++i)
      {
        // We only have std::move() constructors so make a copy of our data.
        arma::mat referenceCopy(referenceData);
@@@ -360,7 -358,7 +362,7 @@@ BOOST_AUTO_TEST_CASE(KNNModelMonochroma
    arma::mat referenceData = arma::randu<arma::mat>(10, 200);
  
    // Build all the possible models.
-   KNNModel models[22];
 -  KNNModel models[20];
++  KNNModel models[24];
    models[0] = KNNModel(KNNModel::TreeTypes::KD_TREE, true);
    models[1] = KNNModel(KNNModel::TreeTypes::KD_TREE, false);
    models[2] = KNNModel(KNNModel::TreeTypes::COVER_TREE, true);
@@@ -379,10 -377,8 +381,12 @@@
    models[15] = KNNModel(KNNModel::TreeTypes::R_PLUS_TREE, false);
    models[16] = KNNModel(KNNModel::TreeTypes::R_PLUS_PLUS_TREE, true);
    models[17] = KNNModel(KNNModel::TreeTypes::R_PLUS_PLUS_TREE, false);
-   models[18] = KNNModel(KNNModel::TreeTypes::RP_TREE, true);
-   models[19] = KNNModel(KNNModel::TreeTypes::RP_TREE, false);
-   models[20] = KNNModel(KNNModel::TreeTypes::MAX_SPLIT_RP_TREE, true);
-   models[21] = KNNModel(KNNModel::TreeTypes::MAX_SPLIT_RP_TREE, false);
+   models[18] = KNNModel(KNNModel::TreeTypes::VP_TREE, true);
+   models[19] = KNNModel(KNNModel::TreeTypes::VP_TREE, false);
++  models[20] = KNNModel(KNNModel::TreeTypes::RP_TREE, true);
++  models[21] = KNNModel(KNNModel::TreeTypes::RP_TREE, false);
++  models[22] = KNNModel(KNNModel::TreeTypes::MAX_SPLIT_RP_TREE, true);
++  models[23] = KNNModel(KNNModel::TreeTypes::MAX_SPLIT_RP_TREE, false);
  
    for (size_t j = 0; j < 2; ++j)
    {
@@@ -392,7 -388,7 +396,7 @@@
      arma::mat distancesExact;
      exact.Search(3, neighborsExact, distancesExact);
  
-     for (size_t i = 0; i < 22; ++i)
 -    for (size_t i = 0; i < 20; ++i)
++    for (size_t i = 0; i < 24; ++i)
      {
        // We only have a std::move() constructor... so copy the data.
        arma::mat referenceCopy(referenceData);
diff --cc src/mlpack/tests/knn_test.cpp
index fe91ab3,ffb6412..a5ce416
--- a/src/mlpack/tests/knn_test.cpp
+++ b/src/mlpack/tests/knn_test.cpp
@@@ -977,7 -977,7 +977,7 @@@ BOOST_AUTO_TEST_CASE(KNNModelTest
    arma::mat referenceData = arma::randu<arma::mat>(10, 200);
  
    // Build all the possible models.
-   KNNModel models[22];
 -  KNNModel models[20];
++  KNNModel models[24];
    models[0] = KNNModel(KNNModel::TreeTypes::KD_TREE, true);
    models[1] = KNNModel(KNNModel::TreeTypes::KD_TREE, false);
    models[2] = KNNModel(KNNModel::TreeTypes::COVER_TREE, true);
@@@ -996,10 -996,8 +996,12 @@@
    models[15] = KNNModel(KNNModel::TreeTypes::R_PLUS_TREE, false);
    models[16] = KNNModel(KNNModel::TreeTypes::R_PLUS_PLUS_TREE, true);
    models[17] = KNNModel(KNNModel::TreeTypes::R_PLUS_PLUS_TREE, false);
-   models[18] = KNNModel(KNNModel::TreeTypes::RP_TREE, true);
-   models[19] = KNNModel(KNNModel::TreeTypes::RP_TREE, false);
-   models[20] = KNNModel(KNNModel::TreeTypes::MAX_SPLIT_RP_TREE, true);
-   models[21] = KNNModel(KNNModel::TreeTypes::MAX_SPLIT_RP_TREE, false);
+   models[18] = KNNModel(KNNModel::TreeTypes::VP_TREE, true);
+   models[19] = KNNModel(KNNModel::TreeTypes::VP_TREE, false);
++  models[20] = KNNModel(KNNModel::TreeTypes::RP_TREE, true);
++  models[21] = KNNModel(KNNModel::TreeTypes::RP_TREE, false);
++  models[22] = KNNModel(KNNModel::TreeTypes::MAX_SPLIT_RP_TREE, true);
++  models[23] = KNNModel(KNNModel::TreeTypes::MAX_SPLIT_RP_TREE, false);
  
    for (size_t j = 0; j < 2; ++j)
    {
@@@ -1009,7 -1007,7 +1011,7 @@@
      arma::mat baselineDistances;
      knn.Search(queryData, 3, baselineNeighbors, baselineDistances);
  
-     for (size_t i = 0; i < 22; ++i)
 -    for (size_t i = 0; i < 20; ++i)
++    for (size_t i = 0; i < 24; ++i)
      {
        // We only have std::move() constructors so make a copy of our data.
        arma::mat referenceCopy(referenceData);
@@@ -1053,7 -1051,7 +1055,7 @@@ BOOST_AUTO_TEST_CASE(KNNModelMonochroma
    arma::mat referenceData = arma::randu<arma::mat>(10, 200);
  
    // Build all the possible models.
-   KNNModel models[22];
 -  KNNModel models[20];
++  KNNModel models[24];
    models[0] = KNNModel(KNNModel::TreeTypes::KD_TREE, true);
    models[1] = KNNModel(KNNModel::TreeTypes::KD_TREE, false);
    models[2] = KNNModel(KNNModel::TreeTypes::COVER_TREE, true);
@@@ -1072,10 -1070,8 +1074,12 @@@
    models[15] = KNNModel(KNNModel::TreeTypes::R_PLUS_TREE, false);
    models[16] = KNNModel(KNNModel::TreeTypes::R_PLUS_PLUS_TREE, true);
    models[17] = KNNModel(KNNModel::TreeTypes::R_PLUS_PLUS_TREE, false);
-   models[18] = KNNModel(KNNModel::TreeTypes::RP_TREE, true);
-   models[19] = KNNModel(KNNModel::TreeTypes::RP_TREE, false);
-   models[20] = KNNModel(KNNModel::TreeTypes::MAX_SPLIT_RP_TREE, true);
-   models[21] = KNNModel(KNNModel::TreeTypes::MAX_SPLIT_RP_TREE, false);
+   models[18] = KNNModel(KNNModel::TreeTypes::VP_TREE, true);
+   models[19] = KNNModel(KNNModel::TreeTypes::VP_TREE, false);
++  models[20] = KNNModel(KNNModel::TreeTypes::RP_TREE, true);
++  models[21] = KNNModel(KNNModel::TreeTypes::RP_TREE, false);
++  models[22] = KNNModel(KNNModel::TreeTypes::MAX_SPLIT_RP_TREE, true);
++  models[23] = KNNModel(KNNModel::TreeTypes::MAX_SPLIT_RP_TREE, false);
  
    for (size_t j = 0; j < 2; ++j)
    {
@@@ -1085,7 -1081,7 +1089,7 @@@
      arma::mat baselineDistances;
      knn.Search(3, baselineNeighbors, baselineDistances);
  
-     for (size_t i = 0; i < 22; ++i)
 -    for (size_t i = 0; i < 20; ++i)
++    for (size_t i = 0; i < 24; ++i)
      {
        // We only have a std::move() constructor... so copy the data.
        arma::mat referenceCopy(referenceData);
diff --cc src/mlpack/tests/range_search_test.cpp
index 217288c,037f593..6c39064
--- a/src/mlpack/tests/range_search_test.cpp
+++ b/src/mlpack/tests/range_search_test.cpp
@@@ -1249,7 -1249,7 +1249,7 @@@ BOOST_AUTO_TEST_CASE(RSModelTest
    arma::mat referenceData = arma::randu<arma::mat>(10, 200);
  
    // Build all the possible models.
-   RSModel models[22];
 -  RSModel models[20];
++  RSModel models[24];
    models[0] = RSModel(RSModel::TreeTypes::KD_TREE, true);
    models[1] = RSModel(RSModel::TreeTypes::KD_TREE, false);
    models[2] = RSModel(RSModel::TreeTypes::COVER_TREE, true);
@@@ -1268,10 -1268,8 +1268,12 @@@
    models[15] = RSModel(RSModel::TreeTypes::R_PLUS_TREE, false);
    models[16] = RSModel(RSModel::TreeTypes::R_PLUS_PLUS_TREE, true);
    models[17] = RSModel(RSModel::TreeTypes::R_PLUS_PLUS_TREE, false);
-   models[18] = RSModel(RSModel::TreeTypes::RP_TREE, true);
-   models[19] = RSModel(RSModel::TreeTypes::RP_TREE, false);
-   models[20] = RSModel(RSModel::TreeTypes::MAX_SPLIT_RP_TREE, true);
-   models[21] = RSModel(RSModel::TreeTypes::MAX_SPLIT_RP_TREE, false);
+   models[18] = RSModel(RSModel::TreeTypes::VP_TREE, true);
+   models[19] = RSModel(RSModel::TreeTypes::VP_TREE, false);
++  models[20] = RSModel(RSModel::TreeTypes::RP_TREE, true);
++  models[21] = RSModel(RSModel::TreeTypes::RP_TREE, false);
++  models[22] = RSModel(RSModel::TreeTypes::MAX_SPLIT_RP_TREE, true);
++  models[23] = RSModel(RSModel::TreeTypes::MAX_SPLIT_RP_TREE, false);
  
    for (size_t j = 0; j < 2; ++j)
    {
@@@ -1285,7 -1283,7 +1287,7 @@@
      vector<vector<pair<double, size_t>>> baselineSorted;
      SortResults(baselineNeighbors, baselineDistances, baselineSorted);
  
-     for (size_t i = 0; i < 22; ++i)
 -    for (size_t i = 0; i < 20; ++i)
++    for (size_t i = 0; i < 24; ++i)
      {
        // We only have std::move() constructors, so make a copy of our data.
        arma::mat referenceCopy(referenceData);
@@@ -1329,7 -1327,7 +1331,7 @@@ BOOST_AUTO_TEST_CASE(RSModelMonochromat
    arma::mat referenceData = arma::randu<arma::mat>(10, 200);
  
    // Build all the possible models.
-   RSModel models[22];
 -  RSModel models[20];
++  RSModel models[24];
    models[0] = RSModel(RSModel::TreeTypes::KD_TREE, true);
    models[1] = RSModel(RSModel::TreeTypes::KD_TREE, false);
    models[2] = RSModel(RSModel::TreeTypes::COVER_TREE, true);
@@@ -1348,10 -1346,8 +1350,12 @@@
    models[15] = RSModel(RSModel::TreeTypes::R_PLUS_TREE, false);
    models[16] = RSModel(RSModel::TreeTypes::R_PLUS_PLUS_TREE, true);
    models[17] = RSModel(RSModel::TreeTypes::R_PLUS_PLUS_TREE, false);
-   models[18] = RSModel(RSModel::TreeTypes::RP_TREE, true);
-   models[19] = RSModel(RSModel::TreeTypes::RP_TREE, false);
-   models[20] = RSModel(RSModel::TreeTypes::MAX_SPLIT_RP_TREE, true);
-   models[21] = RSModel(RSModel::TreeTypes::MAX_SPLIT_RP_TREE, false);
+   models[18] = RSModel(RSModel::TreeTypes::VP_TREE, true);
+   models[19] = RSModel(RSModel::TreeTypes::VP_TREE, false);
++  models[20] = RSModel(RSModel::TreeTypes::RP_TREE, true);
++  models[21] = RSModel(RSModel::TreeTypes::RP_TREE, false);
++  models[22] = RSModel(RSModel::TreeTypes::MAX_SPLIT_RP_TREE, true);
++  models[23] = RSModel(RSModel::TreeTypes::MAX_SPLIT_RP_TREE, false);
  
    for (size_t j = 0; j < 2; ++j)
    {
@@@ -1364,7 -1360,7 +1368,7 @@@
      vector<vector<pair<double, size_t>>> baselineSorted;
      SortResults(baselineNeighbors, baselineDistances, baselineSorted);
  
-     for (size_t i = 0; i < 22; ++i)
 -    for (size_t i = 0; i < 20; ++i)
++    for (size_t i = 0; i < 24; ++i)
      {
        // We only have std::move() cosntructors, so make a copy of our data.
        arma::mat referenceCopy(referenceData);




More information about the mlpack-git mailing list