The NeighborSearch class is a template class for performing distancebased neighbor searches. More...
Public Types  
typedef TreeType< MetricType, NeighborSearchStat< SortPolicy >, MatType >  Tree 
Convenience typedef. More...  
Public Member Functions  
NeighborSearch (MatType referenceSet, const NeighborSearchMode mode=DUAL_TREE_MODE, const double epsilon=0, const MetricType metric=MetricType())  
Initialize the NeighborSearch object, passing a reference dataset (this is the dataset which is searched). More...  
NeighborSearch (Tree referenceTree, const NeighborSearchMode mode=DUAL_TREE_MODE, const double epsilon=0, const MetricType metric=MetricType())  
Initialize the NeighborSearch object with a copy of the given preconstructed reference tree (this is the tree built on the points that will be searched). More...  
NeighborSearch (const NeighborSearchMode mode=DUAL_TREE_MODE, const double epsilon=0, const MetricType metric=MetricType())  
Create a NeighborSearch object without any reference data. More...  
NeighborSearch (const NeighborSearch &other)  
Construct the NeighborSearch object by copying the given NeighborSearch object. More...  
NeighborSearch (NeighborSearch &&other)  
Construct the NeighborSearch object by taking ownership of the given NeighborSearch object. More...  
~NeighborSearch ()  
Delete the NeighborSearch object. More...  
size_t  BaseCases () const 
Return the total number of base case evaluations performed during the last search. More...  
double  Epsilon () const 
Access the relative error to be considered in approximate search. More...  
double &  Epsilon () 
Modify the relative error to be considered in approximate search. More...  
NeighborSearch &  operator= (const NeighborSearch &other) 
Copy the given NeighborSearch object. More...  
NeighborSearch &  operator= (NeighborSearch &&other) 
Take ownership of the given NeighborSearch object. More...  
const MatType &  ReferenceSet () const 
Access the reference dataset. More...  
const Tree &  ReferenceTree () const 
Access the reference tree. More...  
Tree &  ReferenceTree () 
Modify the reference tree. More...  
size_t  Scores () const 
Return the number of node combination scores during the last search. More...  
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 matrices. More...  
void  Search (Tree &queryTree, const size_t k, arma::Mat< size_t > &neighbors, arma::mat &distances, bool sameSet=false) 
Given a prebuilt query tree, search for the nearest neighbors of each point in the query tree, storing the output in the given matrices. More...  
void  Search (const size_t k, arma::Mat< size_t > &neighbors, arma::mat &distances) 
Search for the nearest neighbors of every point in the reference set. More...  
NeighborSearchMode  SearchMode () const 
Access the search mode. More...  
NeighborSearchMode &  SearchMode () 
Modify the search mode. More...  
template < typename Archive >  
void  serialize (Archive &ar, const uint32_t version) 
Serialize the NeighborSearch model. More...  
void  Train (MatType referenceSet) 
Set the reference set to a new reference set, and build a tree if necessary. More...  
void  Train (Tree referenceTree) 
Set the reference tree to a new reference tree. More...  
Static Public Member Functions  
static double  EffectiveError (arma::mat &foundDistances, arma::mat &realDistances) 
Calculate the average relative error (effective error) between the distances calculated and the true distances provided. More...  
static double  Recall (arma::Mat< size_t > &foundNeighbors, arma::Mat< size_t > &realNeighbors) 
Calculate the recall (% of neighbors found) given the list of found neighbors and the true set of neighbors. More...  
The NeighborSearch class is a template class for performing distancebased neighbor searches.
It takes a query dataset and a reference dataset (or just a reference dataset) and, for each point in the query dataset, finds the k neighbors in the reference dataset which have the 'best' distance according to a given sorting policy. A constructor is given which takes only a reference dataset, and if that constructor is used, the given reference dataset is also used as the query dataset.
The template parameters SortPolicy and Metric define the sort function used and the metric (distance function) used. More information on those classes can be found in the NearestNeighborSort class and the kernel::ExampleKernel class.
SortPolicy  The sort policy for distances; see NearestNeighborSort. 
MetricType  The metric to use for computation. 
MatType  The type of data matrix. 
TreeType  The tree type to use; must adhere to the TreeType API. 
DualTreeTraversalType  The type of dual tree traversal to use (defaults to the tree's default traverser). 
SingleTreeTraversalType  The type of single tree traversal to use (defaults to the tree's default traverser). 
Definition at line 88 of file neighbor_search.hpp.
typedef TreeType<MetricType, NeighborSearchStat<SortPolicy>, MatType> Tree 
Convenience typedef.
Definition at line 92 of file neighbor_search.hpp.
NeighborSearch  (  MatType  referenceSet, 
const NeighborSearchMode  mode = DUAL_TREE_MODE , 

const double  epsilon = 0 , 

const MetricType  metric = MetricType() 

) 
Initialize the NeighborSearch object, passing a reference dataset (this is the dataset which is searched).
Optionally, perform the computation in a different mode. An initialized distance metric can be given, for cases where the metric has internal data (i.e. the distance::MahalanobisDistance class).
This method will move the matrices to internal copies, which are rearranged during treebuilding. You can avoid creating an extra copy by preconstructing the trees, passing std::move(yourReferenceSet).
referenceSet  Set of reference points. 
mode  Neighbor search mode. 
epsilon  Relative approximate error (nonnegative). 
metric  An optional instance of the MetricType class. 
NeighborSearch  (  Tree  referenceTree, 
const NeighborSearchMode  mode = DUAL_TREE_MODE , 

const double  epsilon = 0 , 

const MetricType  metric = MetricType() 

) 
Initialize the NeighborSearch object with a copy of the given preconstructed reference tree (this is the tree built on the points that will be searched).
Optionally, choose to use singletree mode. Naive mode is not available as an option for this constructor. Additionally, an instantiated distance metric can be given, for cases where the distance metric holds data.
This method will copy the given tree. When copies must absolutely be avoided, you can avoid this copy, while taking ownership of the given tree, by passing std::move(yourReferenceTree)
referenceTree  Prebuilt tree for reference points. 
mode  Neighbor search mode. 
epsilon  Relative approximate error (nonnegative). 
metric  Instantiated distance metric. 
NeighborSearch  (  const NeighborSearchMode  mode = DUAL_TREE_MODE , 
const double  epsilon = 0 , 

const MetricType  metric = MetricType() 

) 
Create a NeighborSearch object without any reference data.
If Search() is called before a reference set is set with Train(), an exception will be thrown.
mode  Neighbor search mode. 
epsilon  Relative approximate error (nonnegative). 
metric  Instantiated metric. 
NeighborSearch  (  const NeighborSearch< SortPolicy, MetricType, MatType, TreeType, DualTreeTraversalType, SingleTreeTraversalType > &  other  ) 
Construct the NeighborSearch object by copying the given NeighborSearch object.
other  NeighborSearch object to copy. 
NeighborSearch  (  NeighborSearch< SortPolicy, MetricType, MatType, TreeType, DualTreeTraversalType, SingleTreeTraversalType > &&  other  ) 
Construct the NeighborSearch object by taking ownership of the given NeighborSearch object.
other  NeighborSearch object to take ownership of. 
~NeighborSearch  (  ) 
Delete the NeighborSearch object.
The tree is the only member we are responsible for deleting. The others will take care of themselves.

inline 
Return the total number of base case evaluations performed during the last search.
Definition at line 314 of file neighbor_search.hpp.

static 
Calculate the average relative error (effective error) between the distances calculated and the true distances provided.
The input matrices must have the same size.
Cases where the true distance is zero (the same point) or the calculated distance is SortPolicy::WorstDistance() (didn't find enough points) will be ignored.
foundDistances  Matrix storing lists of calculated distances for each query point. 
realDistances  Matrix storing lists of true best distances for each query point. 

inline 
Access the relative error to be considered in approximate search.
Definition at line 325 of file neighbor_search.hpp.

inline 
Modify the relative error to be considered in approximate search.
Definition at line 327 of file neighbor_search.hpp.
NeighborSearch& operator=  (  const NeighborSearch< SortPolicy, MetricType, MatType, TreeType, DualTreeTraversalType, SingleTreeTraversalType > &  other  ) 
Copy the given NeighborSearch object.
other  NeighborSearch object to copy. 
NeighborSearch& operator=  (  NeighborSearch< SortPolicy, MetricType, MatType, TreeType, DualTreeTraversalType, SingleTreeTraversalType > &&  other  ) 
Take ownership of the given NeighborSearch object.
other  NeighborSearch object to take ownership of. 

static 
Calculate the recall (% of neighbors found) given the list of found neighbors and the true set of neighbors.
The recall returned will be in the range [0, 1].
foundNeighbors  Matrix storing lists of calculated neighbors for each query point. 
realNeighbors  Matrix storing lists of true best neighbors for each query point. 

inline 
Access the reference dataset.
Definition at line 330 of file neighbor_search.hpp.

inline 
Access the reference tree.
Definition at line 333 of file neighbor_search.hpp.

inline 
Modify the reference tree.
Definition at line 335 of file neighbor_search.hpp.

inline 
Return the number of node combination scores during the last search.
Definition at line 317 of file neighbor_search.hpp.
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 matrices.
The matrices will be set to the size of n columns by k rows, where n is the number of points in the query dataset and k is the number of neighbors being searched for.
If querySet contains only a few query points, the extra cost of building a tree on the points for dualtree search may not be warranted, and it may be worthwhile to set singleMode = false (either in the constructor or with SingleMode()).
querySet  Set of query points (can be just one point). 
k  Number of neighbors to search for. 
neighbors  Matrix storing lists of neighbors for each query point. 
distances  Matrix storing distances of neighbors for each query point. 
Referenced by LMetricSearch< TPower >::Search(), CosineSearch::Search(), and PearsonSearch::Search().
void Search  (  Tree &  queryTree, 
const size_t  k,  
arma::Mat< size_t > &  neighbors,  
arma::mat &  distances,  
bool  sameSet = false 

) 
Given a prebuilt query tree, search for the nearest neighbors of each point in the query tree, storing the output in the given matrices.
The matrices will be set to the size of n columns by k rows, where n is the number of points in the query dataset and k is the number of neighbors being searched for.
Note that if you are calling Search() multiple times with a single query tree, you need to reset the bounds in the statistic of each query node, otherwise the result may be wrong! You can do this by calling TreeType::Stat()
.Reset() on each node in the query tree.
queryTree  Tree built on query points. 
k  Number of neighbors to search for. 
neighbors  Matrix storing lists of neighbors for each query point. 
distances  Matrix storing distances of neighbors for each query point. 
sameSet  Denotes whether or not the reference and query sets are the same. 
void Search  (  const size_t  k, 
arma::Mat< size_t > &  neighbors,  
arma::mat &  distances  
) 
Search for the nearest neighbors of every point in the reference set.
This is basically equivalent to calling any other overload of Search() with the reference set as the query set; so, this lets you do allknearestneighbors search. The results are stored in the given matrices. The matrices will be set to the size of n columns by k rows, where n is the number of points in the query dataset and k is the number of neighbors being searched for.
k  Number of neighbors to search for. 
neighbors  Matrix storing lists of neighbors for each query point. 
distances  Matrix storing distances of neighbors for each query point. 

inline 
Access the search mode.
Definition at line 320 of file neighbor_search.hpp.

inline 
Modify the search mode.
Definition at line 322 of file neighbor_search.hpp.
void serialize  (  Archive &  ar, 
const uint32_t  version  
) 
Serialize the NeighborSearch model.
Referenced by NeighborSearch< neighbor::NearestNeighborSort, metric::LMetric< TPower, true > >::ReferenceTree().
void Train  (  MatType  referenceSet  ) 
Set the reference set to a new reference set, and build a tree if necessary.
The dataset is copied by default, but the copy can be avoided by transferring the ownership of the dataset using std::move(). This method is called 'Train()' in order to match the rest of the mlpack abstractions, even though calling this "training" is maybe a bit of a stretch.
referenceSet  New set of reference data. 
Referenced by CosineSearch::CosineSearch(), and PearsonSearch::PearsonSearch().
void Train  (  Tree  referenceTree  ) 
Set the reference tree to a new reference tree.
The tree is copied by default, but the copy can be avoided by using std::move() to transfer the ownership of the tree. This method is called 'Train()' in order to match the rest of the mlpack abstractions, even though calling this "training" is maybe a bit of a stretch.
referenceTree  Prebuilt tree for reference points. 