mlpack  1.0.12
dual_tree_traverser.hpp
Go to the documentation of this file.
1 
14 #ifndef __MLPACK_CORE_TREE_COVER_TREE_DUAL_TREE_TRAVERSER_HPP
15 #define __MLPACK_CORE_TREE_COVER_TREE_DUAL_TREE_TRAVERSER_HPP
16 
17 #include <mlpack/core.hpp>
18 #include <queue>
19 
20 namespace mlpack {
21 namespace tree {
22 
23 template<typename MetricType, typename RootPointPolicy, typename StatisticType>
24 template<typename RuleType>
25 class CoverTree<MetricType, RootPointPolicy, StatisticType>::DualTreeTraverser
26 {
27  public:
31  DualTreeTraverser(RuleType& rule);
32 
39  void Traverse(CoverTree& queryNode, CoverTree& referenceNode);
40 
42  size_t NumPrunes() const { return numPrunes; }
44  size_t& NumPrunes() { return numPrunes; }
45 
48  size_t NumVisited() const { return 0; }
49  size_t NumScores() const { return 0; }
50  size_t NumBaseCases() const { return 0; }
51 
52  private:
54  RuleType& rule;
55 
57  size_t numPrunes;
58 
61  {
65  double score;
67  double baseCase;
69  typename RuleType::TraversalInfoType traversalInfo;
70 
72  bool operator<(const DualCoverTreeMapEntry& other) const
73  {
74  if (score == other.score)
75  return (baseCase < other.baseCase);
76  else
77  return (score < other.score);
78  }
79  };
80 
84  void Traverse(CoverTree& queryNode,
85  std::map<int, std::vector<DualCoverTreeMapEntry> >&
86  referenceMap);
87 
89  void PruneMap(CoverTree& queryNode,
90  std::map<int, std::vector<DualCoverTreeMapEntry> >&
91  referenceMap,
92  std::map<int, std::vector<DualCoverTreeMapEntry> >&
93  childMap);
94 
95  void ReferenceRecursion(CoverTree& queryNode,
96  std::map<int, std::vector<DualCoverTreeMapEntry> >&
97  referenceMap);
98 };
99 
100 }; // namespace tree
101 }; // namespace mlpack
102 
103 // Include implementation.
104 #include "dual_tree_traverser_impl.hpp"
105 
106 #endif
size_t & NumPrunes()
Modify the number of pruned nodes.
bool operator<(const DualCoverTreeMapEntry &other) const
Comparison operator, for sorting within the map.
Linear algebra utility functions, generally performed on matrices or vectors.
Definition: load.hpp:23
CoverTree(const arma::mat &dataset, const double base=2.0, MetricType *metric=NULL)
Create the cover tree with the given dataset and given base.
size_t numPrunes
The number of pruned nodes.
RuleType::TraversalInfoType traversalInfo
The traversal info associated with the call to Score() for this entry.
RuleType & rule
The instantiated rule set for pruning branches.
size_t NumPrunes() const
Get the number of pruned nodes.
A cover tree is a tree specifically designed to speed up nearest-neighbor computation in high-dimensi...
Definition: cover_tree.hpp:95
CoverTree< MetricType, RootPointPolicy, StatisticType > * referenceNode
The node this entry refers to.