mlpack: a scalable c++ machine learning library
mlpack  2.0.2
neighbor_search.hpp
Go to the documentation of this file.
1 
15 #ifndef mlpack_METHODS_NEIGHBOR_SEARCH_NEIGHBOR_SEARCH_HPP
16 #define mlpack_METHODS_NEIGHBOR_SEARCH_NEIGHBOR_SEARCH_HPP
17 
18 #include <mlpack/core.hpp>
19 #include <vector>
20 #include <string>
21 
25 
27 #include "neighbor_search_stat.hpp"
30 
31 namespace mlpack {
32 namespace neighbor {
35 
36 // Forward declaration.
37 template<typename SortPolicy>
38 class NSModel;
39 
61 template<typename SortPolicy = NearestNeighborSort,
62  typename MetricType = mlpack::metric::EuclideanDistance,
63  typename MatType = arma::mat,
64  template<typename TreeMetricType,
65  typename TreeStatType,
66  typename TreeMatType> class TreeType = tree::KDTree,
67  template<typename RuleType> class TraversalType =
68  TreeType<MetricType,
70  MatType>::template DualTreeTraverser>
72 {
73  public:
75  typedef TreeType<MetricType, NeighborSearchStat<SortPolicy>, MatType> Tree;
76 
96  NeighborSearch(const MatType& referenceSet,
97  const bool naive = false,
98  const bool singleMode = false,
99  const MetricType metric = MetricType());
100 
120  NeighborSearch(MatType&& referenceSet,
121  const bool naive = false,
122  const bool singleMode = false,
123  const MetricType metric = MetricType());
124 
151  const bool singleMode = false,
152  const MetricType metric = MetricType());
153 
164  NeighborSearch(const bool naive = false,
165  const bool singleMode = false,
166  const MetricType metric = MetricType());
167 
168 
173  ~NeighborSearch();
174 
183  void Train(const MatType& referenceSet);
184 
193  void Train(MatType&& referenceSet);
194 
198  void Train(Tree* referenceTree);
199 
217  void Search(const MatType& querySet,
218  const size_t k,
219  arma::Mat<size_t>& neighbors,
220  arma::mat& distances);
221 
240  void Search(Tree* queryTree,
241  const size_t k,
242  arma::Mat<size_t>& neighbors,
243  arma::mat& distances);
244 
259  void Search(const size_t k,
260  arma::Mat<size_t>& neighbors,
261  arma::mat& distances);
262 
265  size_t BaseCases() const { return baseCases; }
266 
268  size_t Scores() const { return scores; }
269 
271  bool Naive() const { return naive; }
273  bool& Naive() { return naive; }
274 
276  bool SingleMode() const { return singleMode; }
278  bool& SingleMode() { return singleMode; }
279 
281  const MatType& ReferenceSet() const { return *referenceSet; }
282 
284  template<typename Archive>
285  void Serialize(Archive& ar, const unsigned int /* version */);
286 
287  private:
289  std::vector<size_t> oldFromNewReferences;
293  const MatType* referenceSet;
294 
296  bool treeOwner;
298  bool setOwner;
299 
301  bool naive;
304 
306  MetricType metric;
307 
309  size_t baseCases;
311  size_t scores;
312 
316 
318  friend class NSModel<SortPolicy>;
319 }; // class NeighborSearch
320 
321 } // namespace neighbor
322 } // namespace mlpack
323 
324 // Include implementation.
325 #include "neighbor_search_impl.hpp"
326 
327 // Include convenience typedefs.
328 #include "typedef.hpp"
329 
330 #endif
bool Naive() const
Access whether or not search is done in naive linear scan mode.
BinarySpaceTree< MetricType, StatisticType, MatType, bound::HRectBound, MidpointSplit > KDTree
The standard midpoint-split kd-tree.
Definition: typedef.hpp:65
void Train(const MatType &referenceSet)
Set the reference set to a new reference set, and build a tree if necessary.
const MatType & ReferenceSet() const
Access the reference dataset.
std::vector< size_t > oldFromNewReferences
Permutations of reference points during tree building.
Linear algebra utility functions, generally performed on matrices or vectors.
LMetric< 2, true > EuclideanDistance
The Euclidean (L2) distance.
Definition: lmetric.hpp:114
bool treeNeedsReset
If this is true, the reference tree bounds need to be reset on a call to Search() without a query set...
size_t BaseCases() const
Return the total number of base case evaluations performed during the last search.
Extra data for each node in the tree.
The NeighborSearch class is a template class for performing distance-based neighbor searches...
const MatType * referenceSet
Reference dataset. In some situations we may be the owner of this.
size_t scores
The total number of scores (applicable for non-naive search).
size_t baseCases
The total number of base cases.
bool & SingleMode()
Modify whether or not search is done in single-tree mode.
void Serialize(Archive &ar, const unsigned int)
Serialize the NeighborSearch model.
Tree * referenceTree
Pointer to the root of the reference tree.
This class implements the necessary methods for the SortPolicy template parameter of the NeighborSear...
bool singleMode
Indicates if single-tree search is being used (as opposed to dual-tree).
size_t Scores() const
Return the number of node combination scores during the last search.
bool setOwner
If true, we own the reference set.
bool naive
Indicates if O(n^2) naive search is being used.
bool treeOwner
If true, this object created the trees and is responsible for them.
void Search(const MatType &querySet, const size_t k, arma::Mat< size_t > &neighbors, arma::mat &distances)
For each point in the query set, compute the nearest neighbors and store the output in the given matr...
Include all of the base components required to write mlpack methods, and the main mlpack Doxygen docu...
TreeType< MetricType, NeighborSearchStat< SortPolicy >, MatType > Tree
Convenience typedef.
bool SingleMode() const
Access whether or not search is done in single-tree mode.
MetricType metric
Instantiation of metric.
NeighborSearch(const MatType &referenceSet, const bool naive=false, const bool singleMode=false, const MetricType metric=MetricType())
Initialize the NeighborSearch object, passing a reference dataset (this is the dataset which is searc...
~NeighborSearch()
Delete the NeighborSearch object.
bool & Naive()
Modify whether or not search is done in naive linear scan mode.