[mlpack-svn] r17052 - mlpack/trunk/src/mlpack/core/tree/rectangle_tree
fastlab-svn at coffeetalk-1.cc.gatech.edu
fastlab-svn at coffeetalk-1.cc.gatech.edu
Sun Aug 17 02:31:45 EDT 2014
Author: rcurtin
Date: Sun Aug 17 02:31:45 2014
New Revision: 17052
Log:
First pass: line length, bracket surgery (similar to rocket surgery).
Modified:
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/rectangle_tree/r_star_tree_descent_heuristic.hpp
==============================================================================
--- mlpack/trunk/src/mlpack/core/tree/rectangle_tree/r_star_tree_descent_heuristic.hpp (original)
+++ mlpack/trunk/src/mlpack/core/tree/rectangle_tree/r_star_tree_descent_heuristic.hpp Sun Aug 17 02:31:45 2014
@@ -2,8 +2,8 @@
* @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.
+ * 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
@@ -11,28 +11,32 @@
#include <mlpack/core.hpp>
namespace mlpack {
-namespace tree /** Trees and tree-building procedures. */ {
+namespace tree {
/**
- * 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.
+ * 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.
+ * 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);
+ static size_t ChooseDescentNode(const TreeType* node,
+ const TreeType* insertedNode);
};
}; // namespace tree
Modified: mlpack/trunk/src/mlpack/core/tree/rectangle_tree/r_star_tree_descent_heuristic_impl.hpp
==============================================================================
--- mlpack/trunk/src/mlpack/core/tree/rectangle_tree/r_star_tree_descent_heuristic_impl.hpp (original)
+++ mlpack/trunk/src/mlpack/core/tree/rectangle_tree/r_star_tree_descent_heuristic_impl.hpp Sun Aug 17 02:31:45 2014
@@ -14,78 +14,111 @@
namespace tree {
template<typename TreeType>
-inline size_t RStarTreeDescentHeuristic::ChooseDescentNode(const TreeType* node, const arma::vec& point)
+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->Children()[0]->IsLeaf()) { // If its children are leaf nodes, use minimum overlap to choose.
+ if (node->Children()[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++) {
+ for (size_t i = 0; i < node->NumChildren(); i++)
+ {
double sc = 0;
- for (size_t j = 0; j < node->NumChildren(); j++) {
- if (j != i) {
+ 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->Children()[i]->Bound()[k].Hi());
- double newLow = std::min(point[k], node->Children()[i]->Bound()[k].Lo());
+ for (size_t k = 0; k < node->Bound().Dim(); k++)
+ {
+ double newHigh = std::max(point[k],
+ node->Children()[i]->Bound()[k].Hi());
+ double newLow = std::min(point[k],
+ node->Children()[i]->Bound()[k].Lo());
overlap *= node->Children()[i]->Bound()[k].Hi() < node->Children()[j]->Bound()[k].Lo() || node->Children()[i]->Bound()[k].Lo() > node->Children()[j]->Bound()[k].Hi() ? 0 : std::min(node->Children()[i]->Bound()[k].Hi(), node->Children()[j]->Bound()[k].Hi()) - std::max(node->Children()[i]->Bound()[k].Lo(), node->Children()[j]->Bound()[k].Lo());
newOverlap *= newHigh < node->Children()[j]->Bound()[k].Lo() || newLow > node->Children()[j]->Bound()[k].Hi() ? 0 : std::min(newHigh, node->Children()[j]->Bound()[k].Hi()) - std::max(newLow, node->Children()[j]->Bound()[k].Lo());
}
sc += newOverlap - overlap;
}
}
+
originalScores[i] = sc;
- if (sc < origMinScore) {
+ if (sc < origMinScore)
+ {
origMinScore = sc;
bestIndex = i;
- } else if (sc == origMinScore)
+ }
+ 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;
+ 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) {
+ 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++) {
+ for (size_t j = 0; j < node->Bound().Dim(); j++)
+ {
v1 *= node->Children()[i]->Bound()[j].Width();
v2 *= node->Children()[i]->Bound()[j].Contains(point[j]) ? node->Children()[i]->Bound()[j].Width() : (node->Children()[i]->Bound()[j].Hi() < point[j] ? (point[j] - node->Children()[i]->Bound()[j].Lo()) :
- (node->Children()[i]->Bound()[j].Hi() - point[j]));
+ (node->Children()[i]->Bound()[j].Hi() - point[j]));
}
+
assert(v2 - v1 >= 0);
vols[i] = v1;
scores[i] = v2 - v1;
- if (v2 - v1 < minScore) {
+
+ if (v2 - v1 < minScore)
+ {
minScore = v2 - v1;
bestIndex = i;
- } else if (v2 - v1 == minScore)
+ }
+ else if (v2 - v1 == minScore)
+ {
tied = true;
+ }
}
}
- if (tied) { // We break ties by choosing the smallest bound.
+
+ 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) {
+ for (int i = 0; i < scores.size(); i++)
+ {
+ if (scores[i] == minScore)
+ {
+ if (vols[i] < minVol)
+ {
minVol = vols[i];
bestIndex = i;
}
@@ -97,53 +130,71 @@
}
/**
- * 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.
+ * 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)
+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++) {
+
+ for (size_t i = 0; i < node->NumChildren(); i++)
+ {
double v1 = 1.0;
double v2 = 1.0;
- for (size_t j = 0; j < node->Children()[i]->Bound().Dim(); j++) {
+ for (size_t j = 0; j < node->Children()[i]->Bound().Dim(); j++)
+ {
v1 *= node->Children()[i]->Bound()[j].Width();
v2 *= node->Children()[i]->Bound()[j].Contains(insertedNode->Bound()[j]) ? node->Children()[i]->Bound()[j].Width() :
(insertedNode->Bound()[j].Contains(node->Children()[i]->Bound()[j]) ? insertedNode->Bound()[j].Width() : (insertedNode->Bound()[j].Lo() < node->Children()[i]->Bound()[j].Lo() ? (node->Children()[i]->Bound()[j].Hi() - insertedNode->Bound()[j].Lo()) : (insertedNode->Bound()[j].Hi() - node->Children()[i]->Bound()[j].Lo())));
}
+
assert(v2 - v1 >= 0);
vols[i] = v1;
- scores[i] = v2-v1;
- if (v2 - v1 < minScore) {
+ scores[i] = v2 - v1;
+
+ if (v2 - v1 < minScore)
+ {
minScore = v2 - v1;
bestIndex = i;
- } else if(v2 - v1 == minScore)
+ }
+ else if (v2 - v1 == minScore)
+ {
tied = true;
+ }
}
- if(tied) { // We break ties by choosing the smallest bound.
+
+ 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) {
+ 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
+#endif
More information about the mlpack-svn
mailing list