MLPACK  1.0.7
ra_search.hpp
Go to the documentation of this file.
1 
33 #ifndef __MLPACK_METHODS_RANN_RA_SEARCH_HPP
34 #define __MLPACK_METHODS_RANN_RA_SEARCH_HPP
35 
36 #include <mlpack/core.hpp>
37 
39 
42 
43 namespace mlpack {
44 namespace neighbor {
47 
56 template<typename SortPolicy>
58 {
59  private:
61  double bound;
62 
65 
66  public:
71  RAQueryStat() : bound(SortPolicy::WorstDistance()), numSamplesMade(0) { }
72 
76  template<typename TreeType>
77  RAQueryStat(const TreeType& /* node */) :
78  bound(SortPolicy::WorstDistance()),
80  { }
81 
83  double Bound() const { return bound; }
85  double& Bound() { return bound; }
86 
88  size_t NumSamplesMade() const { return numSamplesMade; }
90  size_t& NumSamplesMade() { return numSamplesMade; }
91 };
92 
113 template<typename SortPolicy = NearestNeighborSort,
114  typename MetricType = mlpack::metric::SquaredEuclideanDistance,
116  RAQueryStat<SortPolicy> > >
117 class RASearch
118 {
119  public:
141  RASearch(const typename TreeType::Mat& referenceSet,
142  const typename TreeType::Mat& querySet,
143  const bool naive = false,
144  const bool singleMode = false,
145  const size_t leafSize = 20,
146  const MetricType metric = MetricType());
147 
170  RASearch(const typename TreeType::Mat& referenceSet,
171  const bool naive = false,
172  const bool singleMode = false,
173  const size_t leafSize = 20,
174  const MetricType metric = MetricType());
175 
205  RASearch(TreeType* referenceTree,
206  TreeType* queryTree,
207  const typename TreeType::Mat& referenceSet,
208  const typename TreeType::Mat& querySet,
209  const bool singleMode = false,
210  const MetricType metric = MetricType());
211 
239  RASearch(TreeType* referenceTree,
240  const typename TreeType::Mat& referenceSet,
241  const bool singleMode = false,
242  const MetricType metric = MetricType());
243 
248  ~RASearch();
249 
286  void Search(const size_t k,
287  arma::Mat<size_t>& resultingNeighbors,
288  arma::mat& distances,
289  const double tau = 5,
290  const double alpha = 0.95,
291  const bool sampleAtLeaves = false,
292  const bool firstLeafExact = false,
293  const size_t singleSampleLimit = 20);
294 
302  void ResetQueryTree();
303 
304  private:
307  arma::mat referenceCopy;
309  arma::mat queryCopy;
310 
312  const arma::mat& referenceSet;
314  const arma::mat& querySet;
315 
317  TreeType* referenceTree;
319  TreeType* queryTree;
320 
325 
327  bool naive;
330 
332  MetricType metric;
333 
335  std::vector<size_t> oldFromNewReferences;
337  std::vector<size_t> oldFromNewQueries;
338 
341 
346  void ResetRAQueryStat(TreeType* treeNode);
347 }; // class RASearch
348 
349 }; // namespace neighbor
350 }; // namespace mlpack
351 
352 // Include implementation.
353 #include "ra_search_impl.hpp"
354 
355 // Include convenient typedefs.
356 #include "ra_typedef.hpp"
357 
358 #endif
size_t numSamplesMade
The minimum number of samples made by any query in this node.
Definition: ra_search.hpp:64
arma::mat referenceCopy
Copy of reference dataset (if we need it, because tree building modifies it).
Definition: ra_search.hpp:307
double Bound() const
Get the bound.
Definition: ra_search.hpp:83
~RASearch()
Delete the RASearch object.
Extra data for each node in the tree.
Definition: ra_search.hpp:57
bool ownReferenceTree
Indicates if we should free the reference tree at deletion time.
Definition: ra_search.hpp:322
void ResetRAQueryStat(TreeType *treeNode)
bool naive
Indicates if naive random sampling on the set is being used.
Definition: ra_search.hpp:327
LMetric< 2, false > SquaredEuclideanDistance
Definition: lmetric.hpp:99
TreeType * referenceTree
Pointer to the root of the reference tree.
Definition: ra_search.hpp:317
size_t numberOfPrunes
Total number of pruned nodes during the neighbor search.
Definition: ra_search.hpp:340
A binary space partitioning tree, such as a KD-tree or a ball tree.
const arma::mat & querySet
Query dataset (may not be given).
Definition: ra_search.hpp:314
TreeType * queryTree
Pointer to the root of the query tree (might not exist).
Definition: ra_search.hpp:319
std::vector< size_t > oldFromNewQueries
Permutations of query points during tree building.
Definition: ra_search.hpp:337
const arma::mat & referenceSet
Reference dataset.
Definition: ra_search.hpp:312
size_t NumSamplesMade() const
Get the number of samples made.
Definition: ra_search.hpp:88
void Search(const size_t k, arma::Mat< size_t > &resultingNeighbors, arma::mat &distances, const double tau=5, const double alpha=0.95, const bool sampleAtLeaves=false, const bool firstLeafExact=false, const size_t singleSampleLimit=20)
Compute the rank approximate nearest neighbors and store the output in the given matrices.
bool ownQueryTree
Indicates if we should free the query tree at deletion time.
Definition: ra_search.hpp:324
void ResetQueryTree()
This function recursively resets the RAQueryStat of the queryTree to set &#39;bound&#39; to WorstDistance and...
MetricType metric
Instantiation of kernel.
Definition: ra_search.hpp:332
arma::mat queryCopy
Copy of query dataset (if we need it, because tree building modifies it).
Definition: ra_search.hpp:309
double & Bound()
Modify the bound.
Definition: ra_search.hpp:85
std::vector< size_t > oldFromNewReferences
Permutations of reference points during tree building.
Definition: ra_search.hpp:335
RASearch(const typename TreeType::Mat &referenceSet, const typename TreeType::Mat &querySet, const bool naive=false, const bool singleMode=false, const size_t leafSize=20, const MetricType metric=MetricType())
Initialize the RASearch object, passing both a query and reference dataset.
RAQueryStat(const TreeType &)
Initialization for a node.
Definition: ra_search.hpp:77
bool singleMode
Indicates if single-tree search is being used (opposed to dual-tree).
Definition: ra_search.hpp:329
see subsection cli_alt_reg_tut Alternate DET regularization The usual regularized error f $R_ alpha(t)\f $of a node\f $t\f $is given by
Definition: det.txt:367
The RASearch class: This class provides a generic manner to perform rank-approximate search via rando...
Definition: ra_search.hpp:117
size_t & NumSamplesMade()
Modify the number of samples made.
Definition: ra_search.hpp:90
double bound
The bound on the node&#39;s neighbor distances.
Definition: ra_search.hpp:61
RAQueryStat()
Initialize the statistic with the worst possible distance according to our sorting policy...
Definition: ra_search.hpp:71