mlpack  2.0.1
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/core.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<typename SortPolicy>
43 class RAModel;
44 
67 template<typename SortPolicy = NearestNeighborSort,
68  typename MetricType = metric::EuclideanDistance,
69  typename MatType = arma::mat,
70  template<typename TreeMetricType,
71  typename TreeStatType,
72  typename TreeMatType> class TreeType = tree::KDTree>
73 class RASearch
74 {
75  public:
77  typedef TreeType<MetricType, RAQueryStat<SortPolicy>, MatType> Tree;
78 
124  RASearch(const MatType& referenceSet,
125  const bool naive = false,
126  const bool singleMode = false,
127  const double tau = 5,
128  const double alpha = 0.95,
129  const bool sampleAtLeaves = false,
130  const bool firstLeafExact = false,
131  const size_t singleSampleLimit = 20,
132  const MetricType metric = MetricType());
133 
178  RASearch(MatType&& referenceSet,
179  const bool naive = false,
180  const bool singleMode = false,
181  const double tau = 5,
182  const double alpha = 0.95,
183  const bool sampleAtLeaves = false,
184  const bool firstLeafExact = false,
185  const size_t singleSampleLimit = 20,
186  const MetricType metric = MetricType());
187 
236  RASearch(Tree* referenceTree,
237  const bool singleMode = false,
238  const double tau = 5,
239  const double alpha = 0.95,
240  const bool sampleAtLeaves = false,
241  const bool firstLeafExact = false,
242  const size_t singleSampleLimit = 20,
243  const MetricType metric = MetricType());
244 
264  RASearch(const bool naive = false,
265  const bool singleMode = false,
266  const double tau = 5,
267  const double alpha = 0.95,
268  const bool sampleAtLeaves = false,
269  const bool firstLeafExact = false,
270  const size_t singleSampleLimit = 20,
271  const MetricType metric = MetricType());
272 
277  ~RASearch();
278 
288  void Train(const MatType& referenceSet);
289 
299  void Train(MatType&& referenceSet);
300 
317  void Search(const MatType& querySet,
318  const size_t k,
319  arma::Mat<size_t>& neighbors,
320  arma::mat& distances);
321 
345  void Search(Tree* queryTree,
346  const size_t k,
347  arma::Mat<size_t>& neighbors,
348  arma::mat& distances);
349 
362  void Search(const size_t k,
363  arma::Mat<size_t>& neighbors,
364  arma::mat& distances);
365 
379  void ResetQueryTree(Tree* queryTree) const;
380 
382  const MatType& ReferenceSet() const { return *referenceSet; }
383 
385  bool Naive() const { return naive; }
387  bool& Naive() { return naive; }
388 
390  bool SingleMode() const { return singleMode; }
392  bool& SingleMode() { return singleMode; }
393 
395  double Tau() const { return tau; }
397  double& Tau() { return tau; }
398 
400  double Alpha() const { return alpha; }
402  double& Alpha() { return alpha; }
403 
405  bool SampleAtLeaves() const { return sampleAtLeaves; }
407  bool& SampleAtLeaves() { return sampleAtLeaves; }
408 
410  bool FirstLeafExact() const { return firstLeafExact; }
412  bool& FirstLeafExact() { return firstLeafExact; }
413 
415  size_t SingleSampleLimit() const { return singleSampleLimit; }
417  size_t& SingleSampleLimit() { return singleSampleLimit; }
418 
420  template<typename Archive>
421  void Serialize(Archive& ar, const unsigned int /* version */);
422 
423  private:
425  std::vector<size_t> oldFromNewReferences;
429  const MatType* referenceSet;
430 
432  bool treeOwner;
434  bool setOwner;
435 
437  bool naive;
440 
442  double tau;
444  double alpha;
452 
454  MetricType metric;
455 
457  friend class RAModel<SortPolicy>;
458 }; // class RASearch
459 
460 } // namespace neighbor
461 } // namespace mlpack
462 
463 // Include implementation.
464 #include "ra_search_impl.hpp"
465 
466 // Include convenient typedefs.
467 #include "ra_typedef.hpp"
468 
469 #endif
TreeType< MetricType, RAQueryStat< SortPolicy >, MatType > Tree
Convenience typedef.
Definition: ra_search.hpp:77
BinarySpaceTree< MetricType, StatisticType, MatType, bound::HRectBound, MidpointSplit > KDTree
The standard midpoint-split kd-tree.
Definition: typedef.hpp:65
Linear algebra utility functions, generally performed on matrices or vectors.
bool singleMode
Indicates if single-tree search is being used (opposed to dual-tree).
Definition: ra_search.hpp:439
bool & SampleAtLeaves()
Modify whether or not sampling is done at the leaves.
Definition: ra_search.hpp:407
bool SampleAtLeaves() const
Get whether or not sampling is done at the leaves.
Definition: ra_search.hpp:405
LMetric< 2, true > EuclideanDistance
The Euclidean (L2) distance.
Definition: lmetric.hpp:113
double Tau() const
Get the rank-approximation in percentile of the data.
Definition: ra_search.hpp:395
bool SingleMode() const
Get whether or not single-tree search is used.
Definition: ra_search.hpp:390
bool & FirstLeafExact()
Modify whether or not we traverse to the first leaf without approximation.
Definition: ra_search.hpp:412
bool firstLeafExact
If true, we will traverse to the first leaf without approximation.
Definition: ra_search.hpp:448
size_t & SingleSampleLimit()
Modify the limit on the size of a node that can be approximation.
Definition: ra_search.hpp:417
size_t singleSampleLimit
The limit on the number of points in the largest node that can be approximated by sampling...
Definition: ra_search.hpp:451
Tree * referenceTree
Pointer to the root of the reference tree.
Definition: ra_search.hpp:427
bool & Naive()
Modify whether or not naive (brute-force) search is used.
Definition: ra_search.hpp:387
void Train(const MatType &referenceSet)
"Train" the model on the given reference set.
size_t SingleSampleLimit() const
Get the limit on the size of a node that can be approximated.
Definition: ra_search.hpp:415
MetricType metric
Instantiation of kernel.
Definition: ra_search.hpp:454
bool sampleAtLeaves
Whether or not sampling is done at the leaves. Faster, but less accurate.
Definition: ra_search.hpp:446
const MatType & ReferenceSet() const
Access the reference set.
Definition: ra_search.hpp:382
bool setOwner
If true, we are responsible for deleting the dataset.
Definition: ra_search.hpp:434
bool naive
Indicates if naive random sampling on the set is being used.
Definition: ra_search.hpp:437
double & Tau()
Modify the rank-approximation in percentile of the data.
Definition: ra_search.hpp:397
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...
Include all of the base components required to write MLPACK methods, and the main MLPACK Doxygen docu...
double alpha
The desired success probability (between 0 and 1).
Definition: ra_search.hpp:444
const MatType * referenceSet
Reference dataset. In some situations we may own this dataset.
Definition: ra_search.hpp:429
~RASearch()
Delete the RASearch object.
double Alpha() const
Get the desired success probability.
Definition: ra_search.hpp:400
void Serialize(Archive &ar, const unsigned int)
Serialize the object.
bool & SingleMode()
Modify whether or not single-tree search is used.
Definition: ra_search.hpp:392
std::vector< size_t > oldFromNewReferences
Permutations of reference points during tree building.
Definition: ra_search.hpp:425
void ResetQueryTree(Tree *queryTree) const
This function recursively resets the RAQueryStat of the given query tree to set &#39;bound&#39; to SortPolicy...
bool Naive() const
Get whether or not naive (brute-force) search is used.
Definition: ra_search.hpp:385
bool FirstLeafExact() const
Get whether or not we traverse to the first leaf without approximation.
Definition: ra_search.hpp:410
RASearch(const 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...
double & Alpha()
Modify the desired success probability.
Definition: ra_search.hpp:402
The RASearch class: This class provides a generic manner to perform rank-approximate search via rando...
Definition: ra_search.hpp:73
bool treeOwner
If true, this object created the trees and is responsible for them.
Definition: ra_search.hpp:432
The RAModel class provides an abstraction for the RASearch class, abstracting away the TreeType param...
Definition: ra_model.hpp:37
double tau
The rank-approximation in percentile of the data (between 0 and 100).
Definition: ra_search.hpp:442