ra_search.hpp
Go to the documentation of this file.
1 
25 #ifndef MLPACK_METHODS_RANN_RA_SEARCH_HPP
26 #define MLPACK_METHODS_RANN_RA_SEARCH_HPP
27 
28 #include <mlpack/prereqs.hpp>
29 
31 
34 
35 #include "ra_query_stat.hpp"
36 #include "ra_util.hpp"
37 
38 namespace mlpack {
39 namespace neighbor {
40 
41 // Forward declaration.
42 template<template<typename TreeMetricType,
43  typename TreeStatType,
44  typename TreeMatType> class TreeType>
45 class LeafSizeRAWrapper;
46 
71 template<typename SortPolicy = NearestNeighborSort,
72  typename MetricType = metric::EuclideanDistance,
73  typename MatType = arma::mat,
74  template<typename TreeMetricType,
75  typename TreeStatType,
76  typename TreeMatType> class TreeType = tree::KDTree>
77 class RASearch
78 {
79  public:
81  typedef TreeType<MetricType, RAQueryStat<SortPolicy>, MatType> Tree;
82 
128  RASearch(MatType referenceSet,
129  const bool naive = false,
130  const bool singleMode = false,
131  const double tau = 5,
132  const double alpha = 0.95,
133  const bool sampleAtLeaves = false,
134  const bool firstLeafExact = false,
135  const size_t singleSampleLimit = 20,
136  const MetricType metric = MetricType());
137 
185  RASearch(Tree* referenceTree,
186  const bool singleMode = false,
187  const double tau = 5,
188  const double alpha = 0.95,
189  const bool sampleAtLeaves = false,
190  const bool firstLeafExact = false,
191  const size_t singleSampleLimit = 20,
192  const MetricType metric = MetricType());
193 
213  RASearch(const bool naive = false,
214  const bool singleMode = false,
215  const double tau = 5,
216  const double alpha = 0.95,
217  const bool sampleAtLeaves = false,
218  const bool firstLeafExact = false,
219  const size_t singleSampleLimit = 20,
220  const MetricType metric = MetricType());
221 
226  ~RASearch();
227 
237  void Train(MatType referenceSet);
238 
242  void Train(Tree* referenceTree);
243 
260  void Search(const MatType& querySet,
261  const size_t k,
262  arma::Mat<size_t>& neighbors,
263  arma::mat& distances);
264 
287  void Search(Tree* queryTree,
288  const size_t k,
289  arma::Mat<size_t>& neighbors,
290  arma::mat& distances);
291 
304  void Search(const size_t k,
305  arma::Mat<size_t>& neighbors,
306  arma::mat& distances);
307 
321  void ResetQueryTree(Tree* queryTree) const;
322 
324  const MatType& ReferenceSet() const { return *referenceSet; }
325 
327  bool Naive() const { return naive; }
329  bool& Naive() { return naive; }
330 
332  bool SingleMode() const { return singleMode; }
334  bool& SingleMode() { return singleMode; }
335 
337  double Tau() const { return tau; }
339  double& Tau() { return tau; }
340 
342  double Alpha() const { return alpha; }
344  double& Alpha() { return alpha; }
345 
347  bool SampleAtLeaves() const { return sampleAtLeaves; }
349  bool& SampleAtLeaves() { return sampleAtLeaves; }
350 
352  bool FirstLeafExact() const { return firstLeafExact; }
354  bool& FirstLeafExact() { return firstLeafExact; }
355 
357  size_t SingleSampleLimit() const { return singleSampleLimit; }
359  size_t& SingleSampleLimit() { return singleSampleLimit; }
360 
362  template<typename Archive>
363  void serialize(Archive& ar, const uint32_t /* version */);
364 
365  private:
367  std::vector<size_t> oldFromNewReferences;
369  Tree* referenceTree;
371  const MatType* referenceSet;
372 
374  bool treeOwner;
376  bool setOwner;
377 
379  bool naive;
381  bool singleMode;
382 
384  double tau;
386  double alpha;
388  bool sampleAtLeaves;
390  bool firstLeafExact;
393  size_t singleSampleLimit;
394 
396  MetricType metric;
397 
399  friend class LeafSizeRAWrapper<TreeType>;
400 }; // class RASearch
401 
402 } // namespace neighbor
403 } // namespace mlpack
404 
405 // Include implementation.
406 #include "ra_search_impl.hpp"
407 
408 // Include convenient typedefs.
409 #include "ra_typedef.hpp"
410 
411 #endif
RASearch(MatType referenceSet, const bool naive=false, const bool singleMode=false, const double tau=5, const double alpha=0.95, const bool sampleAtLeaves=false, const bool firstLeafExact=false, const size_t singleSampleLimit=20, const MetricType metric=MetricType())
Initialize the RASearch object, passing both a reference dataset (this is the dataset that will be se...
size_t SingleSampleLimit() const
Get the limit on the size of a node that can be approximated.
Definition: ra_search.hpp:357
bool SampleAtLeaves() const
Get whether or not sampling is done at the leaves.
Definition: ra_search.hpp:347
void Train(MatType referenceSet)
"Train" the model on the given reference set.
Linear algebra utility functions, generally performed on matrices or vectors.
The core includes that mlpack expects; standard C++ includes and Armadillo.
bool & SingleMode()
Modify whether or not single-tree search is used.
Definition: ra_search.hpp:334
size_t & SingleSampleLimit()
Modify the limit on the size of a node that can be approximation.
Definition: ra_search.hpp:359
double & Tau()
Modify the rank-approximation in percentile of the data.
Definition: ra_search.hpp:339
TreeType< MetricType, RAQueryStat< SortPolicy >, MatType > Tree
Convenience typedef.
Definition: ra_search.hpp:81
bool Naive() const
Get whether or not naive (brute-force) search is used.
Definition: ra_search.hpp:327
bool FirstLeafExact() const
Get whether or not we traverse to the first leaf without approximation.
Definition: ra_search.hpp:352
void ResetQueryTree(Tree *queryTree) const
This function recursively resets the RAQueryStat of the given query tree to set &#39;bound&#39; to SortPolicy...
bool SingleMode() const
Get whether or not single-tree search is used.
Definition: ra_search.hpp:332
LeafSizeRAWrapper wraps any RASearch type that needs to be able to take the leaf size into account wh...
Definition: ra_model.hpp:208
bool & Naive()
Modify whether or not naive (brute-force) search is used.
Definition: ra_search.hpp:329
bool & FirstLeafExact()
Modify whether or not we traverse to the first leaf without approximation.
Definition: ra_search.hpp:354
The RASearch class: This class provides a generic manner to perform rank-approximate search via rando...
Definition: ra_search.hpp:77
bool & SampleAtLeaves()
Modify whether or not sampling is done at the leaves.
Definition: ra_search.hpp:349
const MatType & ReferenceSet() const
Access the reference set.
Definition: ra_search.hpp:324
void Search(const MatType &querySet, const size_t k, arma::Mat< size_t > &neighbors, arma::mat &distances)
Compute the rank approximate nearest neighbors of each query point in the query set and store the out...
BinarySpaceTree< MetricType, StatisticType, MatType, bound::HRectBound, MidpointSplit > KDTree
The standard midpoint-split kd-tree.
Definition: typedef.hpp:63
LMetric< 2, true > EuclideanDistance
The Euclidean (L2) distance.
Definition: lmetric.hpp:112
void serialize(Archive &ar, const uint32_t)
Serialize the object.
~RASearch()
Delete the RASearch object.
double & Alpha()
Modify the desired success probability.
Definition: ra_search.hpp:344
double Tau() const
Get the rank-approximation in percentile of the data.
Definition: ra_search.hpp:337
double Alpha() const
Get the desired success probability.
Definition: ra_search.hpp:342