[mlpack-svn] r16543 - in mlpack/trunk/src/mlpack/core/tree: . rectangle_tree
fastlab-svn at coffeetalk-1.cc.gatech.edu
fastlab-svn at coffeetalk-1.cc.gatech.edu
Thu May 22 14:41:17 EDT 2014
Author: andrewmw94
Date: Thu May 22 14:41:17 2014
New Revision: 16543
Log:
add a short and hopefully useful explanation of what different files are for, focusing on BSP trees.
Added:
mlpack/trunk/src/mlpack/core/tree/TREE_EXPLANATION.txt
Modified:
mlpack/trunk/src/mlpack/core/tree/rectangle_tree/rectangle_tree_impl.hpp
Added: mlpack/trunk/src/mlpack/core/tree/TREE_EXPLANATION.txt
==============================================================================
--- (empty file)
+++ mlpack/trunk/src/mlpack/core/tree/TREE_EXPLANATION.txt Thu May 22 14:41:17 2014
@@ -0,0 +1,90 @@
+An attempt to outline how the trees work. At the top, we have a description of how the tree
+is set up in terms of functionality. Then we state which files are responsible for each function.
+At the bottom, we list the files and explain what each of them does.
+
+
+Since dynamic changes are not supported, there are two main activities on a Binary Space Tree:
+ Building. Which is always bulk loading.
+ Searching.
+
+The trees are designed to allow flexibility. As such, the following classes are coded separately:
+ Bounds. There is currently support for hyperrectangles and hyperspheres.
+ Metrics. The tree supports LMetrics.
+ Splits. The strategy for splitting the tree can be changed.
+ Query rules. The methods for determining which points are selected in a search.
+ Tree traversal. The trees support both single_tree and dual_tree traversal algorithms.
+
+There are also a few miscellanious items for tracking data about the tree and queries.
+
+Below is a more detailed description and the name of the file(s) with the applicable
+functionality. All names are given relative to .../mlpack/src/mlpack/core/tree/ :
+ Bounds.
+ Bounds are used to record the possible location so points in a node. This is used
+ to allow more aggressive pruning of the tree while searching.
+
+ See files: ballbound.hpp, ballbound_impl.hpp, bounds.hpp, hrectbound.hpp,
+ and hrectbound_impl.hpp
+ Metrics.
+ Metrics are used to allow the user to specify different distance metrics.
+ The trees currently support LMetrics.
+
+ See files: ../metrics/ip_metric.hpp, ../metrics/ip_metric_impl.hpp,
+ ../metrics/lmetric.hpp, ../metrics/lmetric_impl.hpp,
+ ../metrics/mahalanobis_distance.hpp, ../metrics/mahalanobis_distance_impl.hpp
+ Splits.
+ Splits are used to allow various algorithms for splitting nodes to be used
+ when building trees.
+
+ See files: binary_space_tree/mean_split.hpp, binary_space_tree/mean_split_impl.hpp
+ Query rules.
+ Queries can be either nearest neighbors or furthest neighbors, so we keep the code
+ for each of these separate.
+
+ See files: ../../methods/neighbor_search/neighbor_search_rules.hpp,
+ and ../../methods/neighbor_search/neighbor_search_rules_impl.hpp.
+ Tree traversal.
+ Tree traversal methods are used to find the points in the tree that would be selected
+ by the Query rules by pruning regions that don't need to be searched.
+
+ See files: binary_space_tree/single_tree_traverser.hpp,
+ binary_space_tree/single_tree_traverser_impl.hpp,
+ binary_space_tree/dual_tree_traverser.hpp,
+ and binary_space_tree/dual_tree_traverser_impl.hpp
+
+
+Below is a list of files and what they do:
+
+../../methods/neighbor_search/neighbor_search_rules.hpp
+../../methods/neighbor_search/neighbor_search_rules_impl.hpp
+ These handle the query rules, which allow us to have different rules to find nearest or furthest neighbor.
+ They also handle "score" and "rescore" which evaluate the nodes of a tree to see if we should search in
+ the subtrees. Lower scores mean the boundary is closer to the query.
+
+../metrics/ip_metric.hpp
+../metrics/ip_metric_impl.hpp
+ Inner product metrics.
+../metrics/lmetric.hpp
+../metrics/lmetric_impl.hpp
+ Lp space metrics.
+../metrics/mahalanobis_distance.hpp
+../metrics/mahalanobis_distance_impl.hpp
+ Mahalanobis distance based metrics.
+ballbound.hpp
+ballbound_impl.hpp
+ Hypersphere bounds. Used to bound the points in a node.
+bounds.hpp
+ Handle the different types of bounds. Currently there are hyperspheres and hyperrectangles.
+binary_space_tree/mean_split.hpp
+binary_space_tree/mean_split_impl.hpp
+ Handles the splitting of a node in the Binary Space Tree. The split is in the dimension with the largest range
+ and the split value is the arithmetic mean of that range.
+binary_space_tree/dual_tree_traverser.hpp
+binary_space_tree/dual_tree_traverser_impl.hpp
+ Traverse two trees to find the neighbors.
+binary_space_tree/single_tree_traverser.hpp
+binary_space_tree/single_tree_traverser_impl.hpp
+ Traverse one tree to find the neighbors.
+hrectbound.hpp
+hrectbound_impl.hpp
+ Hyperrectangle bounds. Used to bound the points in a node.
+
Modified: mlpack/trunk/src/mlpack/core/tree/rectangle_tree/rectangle_tree_impl.hpp
==============================================================================
--- mlpack/trunk/src/mlpack/core/tree/rectangle_tree/rectangle_tree_impl.hpp (original)
+++ mlpack/trunk/src/mlpack/core/tree/rectangle_tree/rectangle_tree_impl.hpp Thu May 22 14:41:17 2014
@@ -13,8 +13,9 @@
namespace tree {
template<typename StatisticType,
- typename MatType>
-RectangleTree<StatisticType, MatType>::RectangleTree()
+ typename MatType,
+ typename SplitType>
+RectangleTree<StatisticType, MatType, SplitType>::RectangleTree()
}; //namespace tree
More information about the mlpack-svn
mailing list