[mlpack-svn] r16836 - in mlpack/trunk/src/mlpack: core/tree core/tree/rectangle_tree methods/neighbor_search tests
fastlab-svn at coffeetalk-1.cc.gatech.edu
fastlab-svn at coffeetalk-1.cc.gatech.edu
Fri Jul 18 16:25:45 EDT 2014
Author: andrewmw94
Date: Fri Jul 18 16:25:45 2014
New Revision: 16836
Log:
R* tree split and descent heuristic.
Added:
mlpack/trunk/src/mlpack/core/tree/rectangle_tree/r_star_tree_descent_heuristic.hpp
mlpack/trunk/src/mlpack/core/tree/rectangle_tree/r_star_tree_descent_heuristic_impl.hpp
Modified:
mlpack/trunk/src/mlpack/core/tree/ (props changed)
mlpack/trunk/src/mlpack/core/tree/CMakeLists.txt
mlpack/trunk/src/mlpack/core/tree/rectangle_tree.hpp
mlpack/trunk/src/mlpack/core/tree/rectangle_tree/r_star_tree_split.hpp
mlpack/trunk/src/mlpack/core/tree/rectangle_tree/r_star_tree_split_impl.hpp
mlpack/trunk/src/mlpack/core/tree/rectangle_tree/r_tree_descent_heuristic_impl.hpp
mlpack/trunk/src/mlpack/core/tree/rectangle_tree/r_tree_split.hpp
mlpack/trunk/src/mlpack/methods/neighbor_search/allknn_main.cpp
mlpack/trunk/src/mlpack/tests/rectangle_tree_test.cpp
Modified: mlpack/trunk/src/mlpack/core/tree/CMakeLists.txt
==============================================================================
--- mlpack/trunk/src/mlpack/core/tree/CMakeLists.txt (original)
+++ mlpack/trunk/src/mlpack/core/tree/CMakeLists.txt Fri Jul 18 16:25:45 2014
@@ -40,6 +40,8 @@
rectangle_tree/r_tree_split_impl.hpp
rectangle_tree/r_tree_descent_heuristic.hpp
rectangle_tree/r_tree_descent_heuristic_impl.hpp
+ rectangle_tree/r_star_tree_descent_heuristic.hpp
+ rectangle_tree/r_star_tree_descent_heuristic_impl.hpp
statistic.hpp
traversal_info.hpp
tree_traits.hpp
Modified: mlpack/trunk/src/mlpack/core/tree/rectangle_tree.hpp
==============================================================================
--- mlpack/trunk/src/mlpack/core/tree/rectangle_tree.hpp (original)
+++ mlpack/trunk/src/mlpack/core/tree/rectangle_tree.hpp Fri Jul 18 16:25:45 2014
@@ -18,7 +18,9 @@
#include "rectangle_tree/dual_tree_traverser.hpp"
#include "rectangle_tree/dual_tree_traverser_impl.hpp"
#include "rectangle_tree/r_tree_split.hpp"
+//#include "rectangle_tree/r_star_tree_split.hpp"
#include "rectangle_tree/r_tree_descent_heuristic.hpp"
+#include "rectangle_tree/r_star_tree_descent_heuristic.hpp"
#include "rectangle_tree/traits.hpp"
#endif
Added: mlpack/trunk/src/mlpack/core/tree/rectangle_tree/r_star_tree_descent_heuristic.hpp
==============================================================================
--- (empty file)
+++ mlpack/trunk/src/mlpack/core/tree/rectangle_tree/r_star_tree_descent_heuristic.hpp Fri Jul 18 16:25:45 2014
@@ -0,0 +1,44 @@
+/**
+ * @file r_star_tree_descent_heuristic.hpp
+ * @author Andrew Wells
+ *
+ * Definition of RStarTreeDescentHeuristic, a class that chooses the best child of a node in
+ * an R tree when inserting a new point.
+ */
+#ifndef __MLPACK_CORE_TREE_RECTANGLE_TREE_R_STAR_TREE_DESCENT_HEURISTIC_HPP
+#define __MLPACK_CORE_TREE_RECTANGLE_TREE_R_STAR_TREE_DESCENT_HEURISTIC_HPP
+
+#include <mlpack/core.hpp>
+
+namespace mlpack {
+namespace tree /** Trees and tree-building procedures. */ {
+
+/**
+ * When descending a Rectangle tree to insert a point, we need to have a way to choose
+ * a child node when the point isn't enclosed by any of them. This heuristic is used to do so.
+ */
+class RStarTreeDescentHeuristic
+{
+ public:
+ /**
+ * Evaluate the node using a hueristic. The heuristic guarantees two things:
+ * 1. If point is contained in (or on) bound, the value returned is zero.
+ * 2. If the point is not contained in (or on) bound, the value returned is greater than zero.
+ *
+ * @param bound The bound used for the node that is being evaluated.
+ * @param point The point that is being inserted.
+ */
+ template<typename TreeType>
+ static size_t ChooseDescentNode(const TreeType* node, const arma::vec& point);
+
+ template<typename TreeType>
+ static size_t ChooseDescentNode(const TreeType* node, const TreeType* insertedNode);
+};
+
+}; // namespace tree
+}; // namespace mlpack
+
+// Include implementation.
+#include "r_star_tree_descent_heuristic_impl.hpp"
+
+#endif
Added: mlpack/trunk/src/mlpack/core/tree/rectangle_tree/r_star_tree_descent_heuristic_impl.hpp
==============================================================================
--- (empty file)
+++ mlpack/trunk/src/mlpack/core/tree/rectangle_tree/r_star_tree_descent_heuristic_impl.hpp Fri Jul 18 16:25:45 2014
@@ -0,0 +1,149 @@
+/**
+ * @file r_star_tree_descent_heuristic_impl.hpp
+ * @author Andrew Wells
+ *
+ * Implementation of RStarTreeDescentHeuristic, a class that chooses the best child of a node in
+ * an R tree when inserting a new point.
+ */
+#ifndef __MLPACK_CORE_TREE_RECTANGLE_TREE_R_STAR_TREE_DESCENT_HEURISTIC_IMPL_HPP
+#define __MLPACK_CORE_TREE_RECTANGLE_TREE_R_STAR_TREE_DESCENT_HEURISTIC_IMPL_HPP
+
+#include "r_star_tree_descent_heuristic.hpp"
+
+namespace mlpack {
+namespace tree {
+
+template<typename TreeType>
+inline size_t RStarTreeDescentHeuristic::ChooseDescentNode(const TreeType* node, const arma::vec& point)
+{
+ bool tiedOne = false;
+ std::vector<double> originalScores(node->NumChildren());
+ double origMinScore = DBL_MAX;
+
+ if (node->Child(0)->IsLeaf()) { // If its children are leaf nodes, use minimum overlap to choose.
+ double bestIndex = 0;
+
+ for (size_t i = 0; i < node->NumChildren(); i++) {
+ double sc = 0;
+ for (size_t j = 0; j < node->NumChildren(); j++) {
+ if (j != i) {
+ double overlap = 1.0;
+ double newOverlap = 1.0;
+ for (size_t k = 0; k < node->Bound().Dim(); k++) {
+ double newHigh = std::max(point[k], node->Child(i)->Bound()[k].Hi());
+ double newLow = std::min(point[k], node->Child(i)->Bound()[k].Lo());
+ overlap *= node->Child(i)->Bound()[k].Hi() < node->Child(j)->Bound()[k].Lo() || node->Child(i)->Bound()[k].Lo() > node->Child(j)->Bound()[k].Hi() ? 0 : std::min(node->Child(i)->Bound()[k].Hi(), node->Child(j)->Bound()[k].Hi()) - std::max(node->Child(i)->Bound()[k].Lo(), node->Child(j)->Bound()[k].Lo());
+ newOverlap *= newHigh < node->Child(j)->Bound()[k].Lo() || newLow > node->Child(j)->Bound()[k].Hi() ? 0 : std::min(newHigh, node->Child(j)->Bound()[k].Hi()) - std::max(newLow, node->Child(j)->Bound()[k].Lo());
+ }
+ sc += newOverlap - overlap;
+ }
+ }
+ originalScores[i] = sc;
+ if (sc < origMinScore) {
+ origMinScore = sc;
+ bestIndex = i;
+ } else if (sc == origMinScore)
+ tiedOne = true;
+ }
+
+ if (!tiedOne)
+ return bestIndex;
+ }
+
+ // We do this if it is not on the second level or if there was a tie.
+ std::vector<double> scores(node->NumChildren());
+ if(tiedOne) { // If the first heuristic was tied, we need to eliminate garbage values.
+ for(size_t i = 0; i < scores.size(); i++)
+ scores[i] = DBL_MAX;
+ }
+ std::vector<int> vols(node->NumChildren());
+ double minScore = DBL_MAX;
+ int bestIndex = 0;
+ bool tied = false;
+
+ for (size_t i = 0; i < node->NumChildren(); i++) {
+ if (!tiedOne || originalScores[i] == origMinScore) {
+ double v1 = 1.0;
+ double v2 = 1.0;
+ for (size_t j = 0; j < node->Bound().Dim(); j++) {
+ v1 *= node->Child(i)->Bound()[j].Width();
+ v2 *= node->Child(i)->Bound()[j].Contains(point[j]) ? node->Child(i)->Bound()[j].Width() : (node->Child(i)->Bound()[j].Hi() < point[j] ? (point[j] - node->Child(i)->Bound()[j].Lo()) :
+ (node->Child(i)->Bound()[j].Hi() - point[j]));
+ }
+ assert(v2 - v1 >= 0);
+ vols[i] = v1;
+ scores[i] = v2 - v1;
+ if (v2 - v1 < minScore) {
+ minScore = v2 - v1;
+ bestIndex = i;
+ } else if (v2 - v1 == minScore)
+ tied = true;
+ }
+ }
+ if (tied) { // We break ties by choosing the smallest bound.
+ double minVol = DBL_MAX;
+ bestIndex = 0;
+ for (int i = 0; i < scores.size(); i++) {
+ if (scores[i] == minScore) {
+ if (vols[i] < minVol) {
+ minVol = vols[i];
+ bestIndex = i;
+ }
+ }
+ }
+ }
+
+ return bestIndex;
+}
+
+/**
+ * We simplify this to the same code as is used in the regular R tree, since the inserted node should always be above
+ * the leaf level. If the tree is eventually changed to support rectangles, this could be changed to match the above code;
+ * however, the paper's explanation for their algorithm seems to indicate the above is more for points than for rectangles.
+ */
+template<typename TreeType>
+inline size_t RStarTreeDescentHeuristic::ChooseDescentNode(const TreeType* node, const TreeType* insertedNode)
+{
+ std::vector<double> scores(node->NumChildren());
+ std::vector<int> vols(node->NumChildren());
+ double minScore = DBL_MAX;
+ int bestIndex = 0;
+ bool tied = false;
+
+ for (size_t i = 0; i < node->NumChildren(); i++) {
+ double v1 = 1.0;
+ double v2 = 1.0;
+ for (size_t j = 0; j < node->Child(i)->Bound().Dim(); j++) {
+ v1 *= node->Child(i)->Bound()[j].Width();
+ v2 *= node->Child(i)->Bound()[j].Contains(insertedNode->Bound()[j]) ? node->Child(i)->Bound()[j].Width() :
+ (insertedNode->Bound()[j].Contains(node->Child(i)->Bound()[j]) ? insertedNode->Bound()[j].Width() : (insertedNode->Bound()[j].Lo() < node->Child(i)->Bound()[j].Lo() ? (node->Child(i)->Bound()[j].Hi() - insertedNode->Bound()[j].Lo()) : (insertedNode->Bound()[j].Hi() - node->Child(i)->Bound()[j].Lo())));
+ }
+ assert(v2 - v1 >= 0);
+ vols[i] = v1;
+ scores[i] = v2-v1;
+ if (v2 - v1 < minScore) {
+ minScore = v2 - v1;
+ bestIndex = i;
+ } else if(v2 - v1 == minScore)
+ tied = true;
+ }
+ if(tied) { // We break ties by choosing the smallest bound.
+ double minVol = DBL_MAX;
+ bestIndex = 0;
+ for(int i = 0; i < scores.size(); i++) {
+ if(scores[i] == minScore) {
+ if(vols[i] < minVol) {
+ minVol = vols[i];
+ bestIndex = i;
+ }
+ }
+ }
+ }
+
+ return bestIndex;
+}
+
+}; // namespace tree
+}; // namespace mlpack
+
+#endif
\ No newline at end of file
Modified: mlpack/trunk/src/mlpack/core/tree/rectangle_tree/r_star_tree_split.hpp
==============================================================================
--- mlpack/trunk/src/mlpack/core/tree/rectangle_tree/r_star_tree_split.hpp (original)
+++ mlpack/trunk/src/mlpack/core/tree/rectangle_tree/r_star_tree_split.hpp Fri Jul 18 16:25:45 2014
@@ -1 +1,63 @@
-
+/**
+ * @file r_tree_star_split.hpp
+ * @author Andrew Wells
+ *
+ * Defintion of the RStarTreeSplit class, a class that splits the nodes of an R tree, starting
+ * at a leaf node and moving upwards if necessary.
+ */
+#ifndef __MLPACK_CORE_TREE_RECTANGLE_TREE_R_STAR_TREE_SPLIT_HPP
+#define __MLPACK_CORE_TREE_RECTANGLE_TREE_R_STAR_TREE_SPLIT_HPP
+
+#include <mlpack/core.hpp>
+
+namespace mlpack {
+namespace tree /** Trees and tree-building procedures. */ {
+
+/**
+ * A Rectangle Tree has new points inserted at the bottom. When these
+ * nodes overflow, we split them, moving up the tree and splitting nodes
+ * as necessary.
+ */
+template<typename DescentType,
+ typename StatisticType,
+ typename MatType>
+class RStarTreeSplit
+{
+public:
+
+/**
+ * Split a leaf node using the algorithm described in "The R*-tree: An Efficient and Robust Access method
+ * for Points and Rectangles." If necessary, this split will propagate
+ * upwards through the tree.
+ */
+static void SplitLeafNode(RectangleTree<RStarTreeSplit<DescentType, StatisticType, MatType>, DescentType, StatisticType, MatType>* tree);
+
+/**
+ * Split a non-leaf node using the "default" algorithm. If this is a root node, the
+ * tree increases in depth.
+ */
+static bool SplitNonLeafNode(RectangleTree<RStarTreeSplit<DescentType, StatisticType, MatType>, DescentType, StatisticType, MatType>* tree);
+
+private:
+/**
+ * Class to allow for faster sorting.
+ */
+class sortStruct {
+ double d;
+ int n;
+};
+
+/**
+ * Comparator for sorting with sortStruct.
+ */
+static bool structComp(const sortStruct& s1, const sortStruct& s2) {
+ return s1.d < s2.d;
+}
+
+}; // namespace tree
+}; // namespace mlpack
+
+// Include implementation
+#include "r_star_tree_split_impl.hpp"
+
+#endif
Modified: mlpack/trunk/src/mlpack/core/tree/rectangle_tree/r_star_tree_split_impl.hpp
==============================================================================
--- mlpack/trunk/src/mlpack/core/tree/rectangle_tree/r_star_tree_split_impl.hpp (original)
+++ mlpack/trunk/src/mlpack/core/tree/rectangle_tree/r_star_tree_split_impl.hpp Fri Jul 18 16:25:45 2014
@@ -1 +1,463 @@
-
+/**
+ * @file r_star_tree_split_impl.hpp
+ * @author Andrew Wells
+ *
+ * Implementation of class (RStarTreeSplit) to split a RectangleTree.
+ */
+#ifndef __MLPACK_CORE_TREE_RECTANGLE_TREE_R_STAR_TREE_SPLIT_IMPL_HPP
+#define __MLPACK_CORE_TREE_RECTANGLE_TREE_R_STAR_TREE_SPLIT_IMPL_HPP
+
+#include "r_star_tree_split.hpp"
+#include "rectangle_tree.hpp"
+#include <mlpack/core/math/range.hpp>
+
+namespace mlpack {
+namespace tree {
+
+/**
+ * We call GetPointSeeds to get the two points which will be the initial points in the new nodes
+ * We then call AssignPointDestNode to assign the remaining points to the two new nodes.
+ * Finally, we delete the old node and insert the new nodes into the tree, spliting the parent
+ * if necessary.
+ */
+template<typename DescentType,
+typename StatisticType,
+typename MatType>
+void RStarTreeSplit<DescentType, StatisticType, MatType>::SplitLeafNode(
+ RectangleTree<RStarTreeSplit<DescentType, StatisticType, MatType>, DescentType, StatisticType, MatType>* tree)
+{
+ // If we are splitting the root node, we need will do things differently so that the constructor
+ // and other methods don't confuse the end user by giving an address of another node.
+ if (tree->Parent() == NULL) {
+ RectangleTree<RStarTreeSplit<DescentType, StatisticType, MatType>, DescentType, StatisticType, MatType>* copy =
+ new RectangleTree<RStarTreeSplit<DescentType, StatisticType, MatType>, DescentType, StatisticType, MatType>(*tree); // We actually want to copy this way. Pointers and everything.
+ copy->Parent() = tree;
+ tree->Count() = 0;
+ tree->NullifyData();
+ tree->Child((tree->NumChildren())++) = copy; // Because this was a leaf node, numChildren must be 0.
+ assert(tree->NumChildren() == 1);
+ RStarTreeSplit<DescentType, StatisticType, MatType>::SplitLeafNode(copy);
+ return;
+ }
+
+ int bestOverlapIndexOnBestAxis;
+ int bestAreaIndexOnBestAxis;
+ bool tiedOnOverlap = false;
+ int bestAxis = 0;
+ double bestAxisScore = DBL_MAX;
+ for(int j = 0; j < tree->Bound().Dim(); j++) {
+ double axisScore = 0.0;
+ // Since we only have points in the leaf nodes, we only need to sort once.
+ std::vector<sortStruct> sorted(tree->Count());
+ for(int i = 0; i < sorted.size(); i++) {
+ sorted[i].d = tree->LocalDataset().col(i)[j];
+ sorted[i].n = i;
+ }
+
+ std::sort(sorted.begin(), sorted.end(), structComp);
+
+ // We'll store each of the three scores for each distribution.
+ std::vector<double> areas(tree->MaxLeafSize() - 2*tree->MinLeafSize() + 2);
+ std::vector<double> margins(tree->MaxLeafSize() - 2*tree->MinLeafSize() + 2);
+ std::vector<double> overlapedAreas(tree->MaxLeafSize() - 2*tree->MinLeafSize() + 2);
+ for(int i = 0; i < areas.size(); i++) {
+ areas[i] = 0.0;
+ margins[i] = 0.0;
+ overlapedAreas[i] = 0.0;
+ }
+
+ for(int i = 0; i < areas.size(); i++) {
+ // The ith arrangement is obtained by placing the first tree->MinLeafSize() + i
+ // points in one rectangle and the rest in another. Then we calculate the three
+ // scores for that distribution.
+
+ int cutOff = tree->MinLeafSize() + i;
+ // We'll calculate the max and min in each dimension by hand to save time.
+ std::vector<double> maxG1(tree->Bound().Dim());
+ std::vector<double> minG1(maxG1.size());
+ std::vector<double> maxG2(maxG1.size());
+ std::vector<double> minG2(maxG1.size());
+ for(int k = 0; k < tree->Bound().Dim(); k++) {
+ minG1[k] = maxG1[k] = tree->LocalDataset().col(sorted[0].n)[k];
+ minG2[k] = maxG2[k] = tree->LocalDataset().col(sorted[sorted.size()-1])[k];
+ for(int l = 1; l < tree->Count()-1; l++) {
+ if(l < cutOff) {
+ if(tree->LocalDataset().col(sorted[l].n)[k] < minG1[k])
+ minG1[k] = tree->LocalDataset().col(sorted[l].n)[k];
+ else if(tree->LocalDataset().col(sorted[l].n)[k] > maxG1[k])
+ maxG1[k] = tree->LocalDataset().col(sorted[l].n)[k];
+ } else {
+ if(tree->LocalDataset().col(sorted[l].n)[k] < minG2[k])
+ minG2[k] = tree->LocalDataset().col(sorted[l].n)[k];
+ else if(tree->LocalDataset().col(sorted[l].n)[k] > maxG2[k])
+ maxG2[k] = tree->LocalDataset().col(sorted[l].n)[k];
+ }
+ }
+ }
+ double area1 = 1.0, area2 = 1.0;
+ double oArea = 1.0;
+ for(int k = 0; k < maxG1.size(); k++) {
+ margins[i] += maxG1[k] - minG1[k] + maxG2[k] - minG2[k];
+ area1 *= maxG1[k] - minG1[k];
+ area2 *= maxG2[k] - minG2[k];
+ oArea *= maxG1[k] < minG2[k] || maxG2[k] < minG1[k] ? 0.0 : std::min(maxG1[k], maxG2[k]) - std::max(minG1[k], minG2[k]);
+ }
+ areas[i] += area1 + area2;
+ overlapedAreas[i] += oArea;
+ axisScore += margins[i];
+ }
+ if(axisScore < bestAxisScore) {
+ bestAxisScore = axisScore;
+ bestAxis = j;
+ double bestOverlapIndexOnBestAxis = 0;
+ double bestAreaIndexOnBestAxis = 0;
+ for(int i = 1; i < areas.size(); i++) {
+ if(overlapedAreas[i] < overlapedAreas[bestOverlapIndexOnBestAxis]) {
+ tiedOnOverlap = false;
+ bestAreaIndexOnBestAxis = i;
+ bestOverlapIndexOnBestAxis = i;
+ }
+ else if(overlapedAreas[i] == overlapedAreas[bestOverlapIndexOnBestAxis]) {
+ tiedOnOverlap = true;
+ if(areas[i] < areas[bestAreaIndexOnBestAxis])
+ bestAreaIndexOnBestAxis = i;
+ }
+ }
+ }
+ }
+
+
+ std::vector<sortStruct> sorted(tree->Count());
+ for(int i = 0; i < sorted.size(); i++) {
+ sorted[i].d = tree->LocalDataset().col(i)[bestAxis];
+ sorted[i].n = i;
+ }
+
+ std::sort(sorted.begin(), sorted.end(), structComp);
+
+ RectangleTree<RStarTreeSplit<DescentType, StatisticType, MatType>, DescentType, StatisticType, MatType> *treeOne = new
+ RectangleTree<RStarTreeSplit<DescentType, StatisticType, MatType>, DescentType, StatisticType, MatType>(tree->Parent());
+ RectangleTree<RStarTreeSplit<DescentType, StatisticType, MatType>, DescentType, StatisticType, MatType> *treeTwo = new
+ RectangleTree<RStarTreeSplit<DescentType, StatisticType, MatType>, DescentType, StatisticType, MatType>(tree->Parent());
+
+ if(tiedOnOverlap) {
+ for(int i = 0; i < tree.Count(); i++) {
+ if(i < bestAreaIndexOnBestAxis)
+ treeOne->InsertPoint(tree->Points()[sorted[i].n]);
+ else
+ treeTwo->InsertPoint(tree->Points()[sorted[i].n]);
+ }
+ } else {
+ for(int i = 0; i < tree.Count(); i++) {
+ if(i < bestOverlapIndexOnBestAxis)
+ treeOne->InsertPoint(tree->Points()[sorted[i].n]);
+ else
+ treeTwo->InsertPoint(tree->Points()[sorted[i].n]);
+ }
+ }
+
+ //Remove this node and insert treeOne and treeTwo
+ RectangleTree<RStarTreeSplit<DescentType, StatisticType, MatType>, DescentType, StatisticType, MatType>* par = tree->Parent();
+ int index = 0;
+ for (int i = 0; i < par->NumChildren(); i++) {
+ if (par->Child(i) == tree) {
+ index = i;
+ break;
+ }
+ }
+ par->Child(index) = treeOne;
+ par->Child(par->NumChildren()++) = treeTwo;
+
+ // we only add one at a time, so we should only need to test for equality
+ // just in case, we use an assert.
+ assert(par->NumChildren() <= par->MaxNumChildren());
+ if (par->NumChildren() == par->MaxNumChildren()) {
+ SplitNonLeafNode(par);
+ }
+
+ assert(treeOne->Parent()->NumChildren() < treeOne->MaxNumChildren());
+ assert(treeOne->Parent()->NumChildren() >= treeOne->MinNumChildren());
+ assert(treeTwo->Parent()->NumChildren() < treeTwo->MaxNumChildren());
+ assert(treeTwo->Parent()->NumChildren() >= treeTwo->MinNumChildren());
+
+ tree->SoftDelete();
+
+ return;
+}
+
+/**
+ * We call GetBoundSeeds to get the two new nodes that this one will be broken
+ * into. Then we call AssignNodeDestNode to move the children of this node
+ * into either of those two nodes. Finally, we delete the now unused information
+ * and recurse up the tree if necessary. We don't need to worry about the bounds
+ * higher up the tree because they were already updated if necessary.
+ */
+template<typename DescentType,
+typename StatisticType,
+typename MatType>
+bool RStarTreeSplit<DescentType, StatisticType, MatType>::SplitNonLeafNode(
+ RectangleTree<RStarTreeSplit<DescentType, StatisticType, MatType>, DescentType, StatisticType, MatType>* tree)
+{
+ // If we are splitting the root node, we need will do things differently so that the constructor
+ // and other methods don't confuse the end user by giving an address of another node.
+ if (tree->Parent() == NULL) {
+ RectangleTree<RStarTreeSplit<DescentType, StatisticType, MatType>, DescentType, StatisticType, MatType>* copy =
+ new RectangleTree<RStarTreeSplit<DescentType, StatisticType, MatType>, DescentType, StatisticType, MatType>(*tree); // We actually want to copy this way. Pointers and everything.
+ copy->Parent() = tree;
+ tree->NumChildren() = 0;
+ tree->NullifyData();
+ tree->Child((tree->NumChildren())++) = copy;
+ RStarTreeSplit<DescentType, StatisticType, MatType>::SplitNonLeafNode(copy);
+ return true;
+ }
+
+ int bestOverlapIndexOnBestAxis;
+ int bestAreaIndexOnBestAxis;
+ bool tiedOnOverlap = false;
+ bool lowIsBest = true;
+ int bestAxis = 0;
+ double bestAxisScore = DBL_MAX;
+ for(int j = 0; j < tree->Bound().Dim(); j++) {
+ double axisScore = 0.0;
+
+ // We'll do Bound().Lo() now and use Bound().Hi() later.
+ std::vector<sortStruct> sorted(tree->Count());
+ for(int i = 0; i < sorted.size(); i++) {
+ sorted[i].d = tree->Child(i)->Bound()[j].Lo();
+ sorted[i].n = i;
+ }
+
+ std::sort(sorted.begin(), sorted.end(), structComp);
+
+ // We'll store each of the three scores for each distribution.
+ std::vector<double> areas(tree->MaxNumChildren() - 2*tree->MinNumChildren() + 2);
+ std::vector<double> margins(tree->MaxNumChildren() - 2*tree->MinNumChildren() + 2);
+ std::vector<double> overlapedAreas(tree->MaxNumChildren() - 2*tree->MinNumChildren() + 2);
+ for(int i = 0; i < areas.size(); i++) {
+ areas[i] = 0.0;
+ margins[i] = 0.0;
+ overlapedAreas[i] = 0.0;
+ }
+
+ for(int i = 0; i < areas.size(); i++) {
+ // The ith arrangement is obtained by placing the first tree->MinNumChildren() + i
+ // points in one rectangle and the rest in another. Then we calculate the three
+ // scores for that distribution.
+
+ int cutOff = tree->MinNumChildren() + i;
+ // We'll calculate the max and min in each dimension by hand to save time.
+ std::vector<double> maxG1(tree->Bound().Dim());
+ std::vector<double> minG1(maxG1.size());
+ std::vector<double> maxG2(maxG1.size());
+ std::vector<double> minG2(maxG1.size());
+ for(int k = 0; k < tree->Bound().Dim(); k++) {
+ minG1[k] = tree->Child(sorted[0].n)->Bound()[k].Lo();
+ maxG1[k] = tree->Child(sorted[0].n)->Bound()[k].Hi();
+ minG2[k] = tree->Child(sorted[sorted.size()-1])->Bound()[k].Lo();
+ maxG2[k] = tree->Child(sorted[sorted.size()-1])->Bound()[k].Hi();
+ for(int l = 1; l < tree->Count()-1; l++) {
+ if(l < cutOff) {
+ if(tree->Child(sorted[l].n)->Bound()[k].Lo() < minG1[k])
+ minG1[k] = tree->Child(sorted[l].n)->Bound()[k].Lo();
+ else if(tree->Child(sorted[l].n)->Bound()[k].Hi() > maxG1[k])
+ maxG1[k] = tree->Child(sorted[l].n)->Bound()[k].Hi();
+ } else {
+ if(tree->Child(sorted[l].n)->Bound()[k].Lo() < minG2[k])
+ minG2[k] = tree->Child(sorted[l].n)->Bound()[k].Lo();
+ else if(tree->Child(sorted[l].n)->Bound()[k].Hi() > maxG2[k])
+ maxG2[k] = tree->Child(sorted[l].n)->Bound()[k].Hi();
+ }
+ }
+ }
+ double area1 = 1.0, area2 = 1.0;
+ double oArea = 1.0;
+ for(int k = 0; k < maxG1.size(); k++) {
+ margins[i] += maxG1[k] - minG1[k] + maxG2[k] - minG2[k];
+ area1 *= maxG1[k] - minG1[k];
+ area2 *= maxG2[k] - minG2[k];
+ oArea *= maxG1[k] < minG2[k] || maxG2[k] < minG1[k] ? 0.0 : std::min(maxG1[k], maxG2[k]) - std::max(minG1[k], minG2[k]);
+ }
+ areas[i] += area1 + area2;
+ overlapedAreas[i] += oArea;
+ axisScore += margins[i];
+ }
+ if(axisScore < bestAxisScore) {
+ bestAxisScore = axisScore;
+ bestAxis = j;
+ double bestOverlapIndexOnBestAxis = 0;
+ double bestAreaIndexOnBestAxis = 0;
+ for(int i = 1; i < areas.size(); i++) {
+ if(overlapedAreas[i] < overlapedAreas[bestOverlapIndexOnBestAxis]) {
+ tiedOnOverlap = false;
+ bestAreaIndexOnBestAxis = i;
+ bestOverlapIndexOnBestAxis = i;
+ }
+ else if(overlapedAreas[i] == overlapedAreas[bestOverlapIndexOnBestAxis]) {
+ tiedOnOverlap = true;
+ if(areas[i] < areas[bestAreaIndexOnBestAxis])
+ bestAreaIndexOnBestAxis = i;
+ }
+ }
+ }
+ }
+ //Now we do the same thing using Bound().Hi() and choose the best of the two.
+ for(int j = 0; j < tree->Bound().Dim(); j++) {
+ double axisScore = 0.0;
+
+ // We'll do Bound().Lo() now and use Bound().Hi() later.
+ std::vector<sortStruct> sorted(tree->Count());
+ for(int i = 0; i < sorted.size(); i++) {
+ sorted[i].d = tree->Child(i)->Bound()[j].Hi();
+ sorted[i].n = i;
+ }
+
+ std::sort(sorted.begin(), sorted.end(), structComp);
+
+ // We'll store each of the three scores for each distribution.
+ std::vector<double> areas(tree->MaxNumChildren() - 2*tree->MinNumChildren() + 2);
+ std::vector<double> margins(tree->MaxNumChildren() - 2*tree->MinNumChildren() + 2);
+ std::vector<double> overlapedAreas(tree->MaxNumChildren() - 2*tree->MinNumChildren() + 2);
+ for(int i = 0; i < areas.size(); i++) {
+ areas[i] = 0.0;
+ margins[i] = 0.0;
+ overlapedAreas[i] = 0.0;
+ }
+
+ for(int i = 0; i < areas.size(); i++) {
+ // The ith arrangement is obtained by placing the first tree->MinNumChildren() + i
+ // points in one rectangle and the rest in another. Then we calculate the three
+ // scores for that distribution.
+
+ int cutOff = tree->MinNumChildren() + i;
+ // We'll calculate the max and min in each dimension by hand to save time.
+ std::vector<double> maxG1(tree->Bound().Dim());
+ std::vector<double> minG1(maxG1.size());
+ std::vector<double> maxG2(maxG1.size());
+ std::vector<double> minG2(maxG1.size());
+ for(int k = 0; k < tree->Bound().Dim(); k++) {
+ minG1[k] = tree->Child(sorted[0].n)->Bound()[k].Lo();
+ maxG1[k] = tree->Child(sorted[0].n)->Bound()[k].Hi();
+ minG2[k] = tree->Child(sorted[sorted.size()-1])->Bound()[k].Lo();
+ maxG2[k] = tree->Child(sorted[sorted.size()-1])->Bound()[k].Hi();
+ for(int l = 1; l < tree->Count()-1; l++) {
+ if(l < cutOff) {
+ if(tree->Child(sorted[l].n)->Bound()[k].Lo() < minG1[k])
+ minG1[k] = tree->Child(sorted[l].n)->Bound()[k].Lo();
+ else if(tree->Child(sorted[l].n)->Bound()[k].Hi() > maxG1[k])
+ maxG1[k] = tree->Child(sorted[l].n)->Bound()[k].Hi();
+ } else {
+ if(tree->Child(sorted[l].n)->Bound()[k].Lo() < minG2[k])
+ minG2[k] = tree->Child(sorted[l].n)->Bound()[k].Lo();
+ else if(tree->Child(sorted[l].n)->Bound()[k].Hi() > maxG2[k])
+ maxG2[k] = tree->Child(sorted[l].n)->Bound()[k].Hi();
+ }
+ }
+ }
+ double area1 = 1.0, area2 = 1.0;
+ double oArea = 1.0;
+ for(int k = 0; k < maxG1.size(); k++) {
+ margins[i] += maxG1[k] - minG1[k] + maxG2[k] - minG2[k];
+ area1 *= maxG1[k] - minG1[k];
+ area2 *= maxG2[k] - minG2[k];
+ oArea *= maxG1[k] < minG2[k] || maxG2[k] < minG1[k] ? 0.0 : std::min(maxG1[k], maxG2[k]) - std::max(minG1[k], minG2[k]);
+ }
+ areas[i] += area1 + area2;
+ overlapedAreas[i] += oArea;
+ axisScore += margins[i];
+ }
+ if(axisScore < bestAxisScore) {
+ bestAxisScore = axisScore;
+ bestAxis = j;
+ lowIsBest = false;
+ double bestOverlapIndexOnBestAxis = 0;
+ double bestAreaIndexOnBestAxis = 0;
+ for(int i = 1; i < areas.size(); i++) {
+ if(overlapedAreas[i] < overlapedAreas[bestOverlapIndexOnBestAxis]) {
+ tiedOnOverlap = false;
+ bestAreaIndexOnBestAxis = i;
+ bestOverlapIndexOnBestAxis = i;
+ }
+ else if(overlapedAreas[i] == overlapedAreas[bestOverlapIndexOnBestAxis]) {
+ tiedOnOverlap = true;
+ if(areas[i] < areas[bestAreaIndexOnBestAxis])
+ bestAreaIndexOnBestAxis = i;
+ }
+ }
+ }
+ }
+
+
+
+
+ std::vector<sortStruct> sorted(tree->NumChildren());
+ if(lowIsBest) {
+ for(int i = 0; i < sorted.size(); i++) {
+ sorted[i].d = tree->Child()->Bound().Lo()[bestAxis];
+ sorted[i].n = i;
+ }
+ } else {
+ for(int i = 0; i < sorted.size(); i++) {
+ sorted[i].d = tree->Child()->Bound().Hi()[bestAxis];
+ sorted[i].n = i;
+ }
+ }
+
+ std::sort(sorted.begin(), sorted.end(), structComp);
+
+ RectangleTree<RStarTreeSplit<DescentType, StatisticType, MatType>, DescentType, StatisticType, MatType> *treeOne = new
+ RectangleTree<RStarTreeSplit<DescentType, StatisticType, MatType>, DescentType, StatisticType, MatType>(tree->Parent());
+ RectangleTree<RStarTreeSplit<DescentType, StatisticType, MatType>, DescentType, StatisticType, MatType> *treeTwo = new
+ RectangleTree<RStarTreeSplit<DescentType, StatisticType, MatType>, DescentType, StatisticType, MatType>(tree->Parent());
+
+ if(tiedOnOverlap) {
+ for(int i = 0; i < tree.Count(); i++) {
+ if(i < bestAreaIndexOnBestAxis)
+ treeOne->InsertPoint(tree->Points()[sorted[i].n]);
+ else
+ treeTwo->InsertPoint(tree->Points()[sorted[i].n]);
+ }
+ } else {
+ for(int i = 0; i < tree.Count(); i++) {
+ if(i < bestOverlapIndexOnBestAxis)
+ treeOne->InsertPoint(tree->Points()[sorted[i].n]);
+ else
+ treeTwo->InsertPoint(tree->Points()[sorted[i].n]);
+ }
+ }
+
+ //Remove this node and insert treeOne and treeTwo
+ RectangleTree<RStarTreeSplit<DescentType, StatisticType, MatType>, DescentType, StatisticType, MatType>* par = tree->Parent();
+ int index = 0;
+ for (int i = 0; i < par->NumChildren(); i++) {
+ if (par->Child(i) == tree) {
+ index = i;
+ break;
+ }
+ }
+ par->Child(index) = treeOne;
+ par->Child(par->NumChildren()++) = treeTwo;
+
+ // we only add one at a time, so we should only need to test for equality
+ // just in case, we use an assert.
+ assert(par->NumChildren() <= par->MaxNumChildren());
+ if (par->NumChildren() == par->MaxNumChildren()) {
+ SplitNonLeafNode(par);
+ }
+
+ assert(treeOne->Parent()->NumChildren() < treeOne->MaxNumChildren());
+ assert(treeOne->Parent()->NumChildren() >= treeOne->MinNumChildren());
+ assert(treeTwo->Parent()->NumChildren() < treeTwo->MaxNumChildren());
+ assert(treeTwo->Parent()->NumChildren() >= treeTwo->MinNumChildren());
+
+ tree->SoftDelete();
+
+ return false;
+}
+
+
+
+
+}; // namespace tree
+}; // namespace mlpack
+
+#endif
Modified: mlpack/trunk/src/mlpack/core/tree/rectangle_tree/r_tree_descent_heuristic_impl.hpp
==============================================================================
--- mlpack/trunk/src/mlpack/core/tree/rectangle_tree/r_tree_descent_heuristic_impl.hpp (original)
+++ mlpack/trunk/src/mlpack/core/tree/rectangle_tree/r_tree_descent_heuristic_impl.hpp Fri Jul 18 16:25:45 2014
@@ -13,51 +13,87 @@
namespace mlpack {
namespace tree {
-// Return the increase in volume required when inserting point into bound.
-
template<typename TreeType>
inline size_t RTreeDescentHeuristic::ChooseDescentNode(const TreeType* node, const arma::vec& point)
{
+ std::vector<double> scores(node->NumChildren());
+ std::vector<int> vols(node->NumChildren());
double minScore = DBL_MAX;
int bestIndex = 0;
+ bool tied = false;
- for (size_t j = 0; j < node->NumChildren(); j++) {
+ for (size_t i = 0; i < node->NumChildren(); i++) {
double v1 = 1.0;
double v2 = 1.0;
- for (size_t i = 0; i < node->Child(j)->Bound().Dim(); i++) {
- v1 *= node->Child(j)->Bound()[i].Width();
- v2 *= node->Child(j)->Bound()[i].Contains(point[i]) ? node->Child(j)->Bound()[i].Width() : (node->Child(j)->Bound()[i].Hi() < point[i] ? (point[i] - node->Child(j)->Bound()[i].Lo()) :
- (node->Child(j)->Bound()[i].Hi() - point[i]));
+ for (size_t j = 0; j < node->Child(i)->Bound().Dim(); j++) {
+ v1 *= node->Child(i)->Bound()[j].Width();
+ v2 *= node->Child(i)->Bound()[j].Contains(point[j]) ? node->Child(i)->Bound()[j].Width() : (node->Child(i)->Bound()[j].Hi() < point[j] ? (point[j] - node->Child(i)->Bound()[j].Lo()) :
+ (node->Child(i)->Bound()[j].Hi() - point[j]));
}
assert(v2 - v1 >= 0);
+ vols[i] = v1;
+ scores[i] = v2-v1;
if (v2 - v1 < minScore) {
minScore = v2 - v1;
- bestIndex = j;
+ bestIndex = i;
+ } else if(v2 - v1 == minScore)
+ tied = true;
+ }
+ if(tied) { // We break ties by choosing the smallest bound.
+ double minVol = DBL_MAX;
+ bestIndex = 0;
+ for(int i = 0; i < scores.size(); i++) {
+ if(scores[i] == minScore) {
+ if(vols[i] < minVol) {
+ minVol = vols[i];
+ bestIndex = i;
+ }
+ }
}
}
+
return bestIndex;
}
template<typename TreeType>
inline size_t RTreeDescentHeuristic::ChooseDescentNode(const TreeType* node, const TreeType* insertedNode)
{
+ std::vector<double> scores(node->NumChildren());
+ std::vector<int> vols(node->NumChildren());
double minScore = DBL_MAX;
int bestIndex = 0;
-
- for (size_t j = 0; j < node->NumChildren(); j++) {
+ bool tied = false;
+
+ for (size_t i = 0; i < node->NumChildren(); i++) {
double v1 = 1.0;
double v2 = 1.0;
- for (size_t i = 0; i < node->Child(j)->Bound().Dim(); i++) {
- v1 *= node->Child(j)->Bound()[i].Width();
- v2 *= node->Child(j)->Bound()[i].Contains(insertedNode->Bound()[i]) ? node->Child(j)->Bound()[i].Width() :
- (insertedNode->Bound()[i].Contains(node->Child(j)->Bound()[i]) ? insertedNode->Bound()[i].Width() : (insertedNode->Bound()[i].Lo() < node->Child(j)->Bound()[i].Lo() ? (node->Child(j)->Bound()[i].Hi() - insertedNode->Bound()[i].Lo()) : (insertedNode->Bound()[i].Hi() - node->Child(j)->Bound()[i].Lo())));
+ for (size_t j = 0; j < node->Child(i)->Bound().Dim(); j++) {
+ v1 *= node->Child(i)->Bound()[j].Width();
+ v2 *= node->Child(i)->Bound()[j].Contains(insertedNode->Bound()[j]) ? node->Child(i)->Bound()[j].Width() :
+ (insertedNode->Bound()[j].Contains(node->Child(i)->Bound()[j]) ? insertedNode->Bound()[j].Width() : (insertedNode->Bound()[j].Lo() < node->Child(i)->Bound()[j].Lo() ? (node->Child(i)->Bound()[j].Hi() - insertedNode->Bound()[j].Lo()) : (insertedNode->Bound()[j].Hi() - node->Child(i)->Bound()[j].Lo())));
}
assert(v2 - v1 >= 0);
+ vols[i] = v1;
+ scores[i] = v2-v1;
if (v2 - v1 < minScore) {
minScore = v2 - v1;
- bestIndex = j;
+ bestIndex = i;
+ } else if(v2 - v1 == minScore)
+ tied = true;
+ }
+ if(tied) { // We break ties by choosing the smallest bound.
+ double minVol = DBL_MAX;
+ bestIndex = 0;
+ for(int i = 0; i < scores.size(); i++) {
+ if(scores[i] == minScore) {
+ if(vols[i] < minVol) {
+ minVol = vols[i];
+ bestIndex = i;
+ }
+ }
}
}
+
return bestIndex;
}
Modified: mlpack/trunk/src/mlpack/core/tree/rectangle_tree/r_tree_split.hpp
==============================================================================
--- mlpack/trunk/src/mlpack/core/tree/rectangle_tree/r_tree_split.hpp (original)
+++ mlpack/trunk/src/mlpack/core/tree/rectangle_tree/r_tree_split.hpp Fri Jul 18 16:25:45 2014
@@ -27,8 +27,7 @@
/**
* Split a leaf node using the "default" algorithm. If necessary, this split will propagate
- * upwards through the tree. The methods for splitting non-leaf nodes are private since
- * they should only be called if a leaf node overflows.
+ * upwards through the tree.
*/
static void SplitLeafNode(RectangleTree<RTreeSplit<DescentType, StatisticType, MatType>, DescentType, StatisticType, MatType>* tree);
Modified: mlpack/trunk/src/mlpack/methods/neighbor_search/allknn_main.cpp
==============================================================================
--- mlpack/trunk/src/mlpack/methods/neighbor_search/allknn_main.cpp (original)
+++ mlpack/trunk/src/mlpack/methods/neighbor_search/allknn_main.cpp Fri Jul 18 16:25:45 2014
@@ -272,8 +272,8 @@
// Because we may construct it differently, we need a pointer.
NeighborSearch<NearestNeighborSort, metric::LMetric<2, true>,
- RectangleTree<tree::RTreeSplit<tree::RTreeDescentHeuristic, NeighborSearchStat<NearestNeighborSort>, arma::mat>,
- tree::RTreeDescentHeuristic,
+ RectangleTree<tree::RTreeSplit<tree::RStarTreeDescentHeuristic, NeighborSearchStat<NearestNeighborSort>, arma::mat>,
+ tree::RStarTreeDescentHeuristic,
NeighborSearchStat<NearestNeighborSort>,
arma::mat> >* allknn = NULL;
@@ -282,14 +282,14 @@
Log::Info << "Building reference tree..." << endl;
Timer::Start("tree_building");
- RectangleTree<tree::RTreeSplit<tree::RTreeDescentHeuristic, NeighborSearchStat<NearestNeighborSort>, arma::mat>,
- tree::RTreeDescentHeuristic,
+ RectangleTree<tree::RTreeSplit<tree::RStarTreeDescentHeuristic, NeighborSearchStat<NearestNeighborSort>, arma::mat>,
+ tree::RStarTreeDescentHeuristic,
NeighborSearchStat<NearestNeighborSort>,
arma::mat>
refTree(referenceData, leafSize, leafSize/3, 5, 2, 0);
- RectangleTree<tree::RTreeSplit<tree::RTreeDescentHeuristic, NeighborSearchStat<NearestNeighborSort>, arma::mat>,
- tree::RTreeDescentHeuristic,
+ RectangleTree<tree::RTreeSplit<tree::RStarTreeDescentHeuristic, NeighborSearchStat<NearestNeighborSort>, arma::mat>,
+ tree::RStarTreeDescentHeuristic,
NeighborSearchStat<NearestNeighborSort>,
arma::mat>*
queryTree = NULL; // Empty for now.
@@ -302,16 +302,16 @@
<< queryData.n_rows << " x " << queryData.n_cols << ")." << endl;
allknn = new NeighborSearch<NearestNeighborSort, metric::LMetric<2, true>,
- RectangleTree<tree::RTreeSplit<tree::RTreeDescentHeuristic, NeighborSearchStat<NearestNeighborSort>, arma::mat>,
- tree::RTreeDescentHeuristic,
+ RectangleTree<tree::RTreeSplit<tree::RStarTreeDescentHeuristic, NeighborSearchStat<NearestNeighborSort>, arma::mat>,
+ tree::RStarTreeDescentHeuristic,
NeighborSearchStat<NearestNeighborSort>,
arma::mat> >(&refTree, queryTree,
referenceData, queryData, singleMode);
} else
{
allknn = new NeighborSearch<NearestNeighborSort, metric::LMetric<2, true>,
- RectangleTree<tree::RTreeSplit<tree::RTreeDescentHeuristic, NeighborSearchStat<NearestNeighborSort>, arma::mat>,
- tree::RTreeDescentHeuristic,
+ RectangleTree<tree::RTreeSplit<tree::RStarTreeDescentHeuristic, NeighborSearchStat<NearestNeighborSort>, arma::mat>,
+ tree::RStarTreeDescentHeuristic,
NeighborSearchStat<NearestNeighborSort>,
arma::mat> >(&refTree,
referenceData, singleMode);
Modified: mlpack/trunk/src/mlpack/tests/rectangle_tree_test.cpp
==============================================================================
--- mlpack/trunk/src/mlpack/tests/rectangle_tree_test.cpp (original)
+++ mlpack/trunk/src/mlpack/tests/rectangle_tree_test.cpp Fri Jul 18 16:25:45 2014
@@ -209,15 +209,15 @@
arma::Mat<size_t> neighbors2;
arma::mat distances2;
- RectangleTree<tree::RTreeSplit<tree::RTreeDescentHeuristic, NeighborSearchStat<NearestNeighborSort>, arma::mat>,
- tree::RTreeDescentHeuristic,
+ RectangleTree<tree::RTreeSplit<tree::RStarTreeDescentHeuristic, NeighborSearchStat<NearestNeighborSort>, arma::mat>,
+ tree::RStarTreeDescentHeuristic,
NeighborSearchStat<NearestNeighborSort>,
arma::mat> RTree(dataset, 20, 6, 5, 2, 0);
// nearest neighbor search with the R tree.
mlpack::neighbor::NeighborSearch<NearestNeighborSort, metric::LMetric<2, true>,
- RectangleTree<tree::RTreeSplit<tree::RTreeDescentHeuristic, NeighborSearchStat<NearestNeighborSort>, arma::mat>,
- tree::RTreeDescentHeuristic,
+ RectangleTree<tree::RTreeSplit<tree::RStarTreeDescentHeuristic, NeighborSearchStat<NearestNeighborSort>, arma::mat>,
+ tree::RStarTreeDescentHeuristic,
NeighborSearchStat<NearestNeighborSort>,
arma::mat> > allknn1(&RTree,
dataset, true);
More information about the mlpack-svn
mailing list