MLPACK  1.0.4
Public Member Functions | Private Attributes
mlpack::neighbor::NeighborSearch< SortPolicy, MetricType, TreeType > Class Template Reference

The NeighborSearch class is a template class for performing distance-based neighbor searches. More...

List of all members.

Public Member Functions

 NeighborSearch (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 NeighborSearch object, passing both a query and reference dataset.
 NeighborSearch (const typename TreeType::Mat &referenceSet, const bool naive=false, const bool singleMode=false, const size_t leafSize=20, const MetricType metric=MetricType())
 Initialize the NeighborSearch object, passing only one dataset, which is used as both the query and the reference dataset.
 NeighborSearch (TreeType *referenceTree, TreeType *queryTree, const typename TreeType::Mat &referenceSet, const typename TreeType::Mat &querySet, const bool singleMode=false, const MetricType metric=MetricType())
 Initialize the NeighborSearch object with the given datasets and pre-constructed trees.
 NeighborSearch (TreeType *referenceTree, const typename TreeType::Mat &referenceSet, const bool singleMode=false, const MetricType metric=MetricType())
 Initialize the NeighborSearch object with the given reference dataset and pre-constructed tree.
 ~NeighborSearch ()
 Delete the NeighborSearch object.
void Search (const size_t k, arma::Mat< size_t > &resultingNeighbors, arma::mat &distances)
 Compute the nearest neighbors and store the output in the given matrices.

Private Attributes

MetricType metric
 Instantiation of kernel.
bool naive
 Indicates if O(n^2) naive search is being used.
size_t numberOfPrunes
 Total number of pruned nodes during the neighbor search.
std::vector< size_t > oldFromNewQueries
 Permutations of query points during tree building.
std::vector< size_t > oldFromNewReferences
 Permutations of reference points during tree building.
bool ownQueryTree
 Indicates if we should free the query tree at deletion time.
bool ownReferenceTree
 Indicates if we should free the reference tree at deletion time.
arma::mat queryCopy
 Copy of query dataset (if we need it, because tree building modifies it).
const arma::mat & querySet
 Query dataset (may not be given).
TreeType * queryTree
 Pointer to the root of the query tree (might not exist).
arma::mat referenceCopy
 Copy of reference dataset (if we need it, because tree building modifies it).
const arma::mat & referenceSet
 Reference dataset.
TreeType * referenceTree
 Pointer to the root of the reference tree.
bool singleMode
 Indicates if single-tree search is being used (opposed to dual-tree).

Detailed Description

template<typename SortPolicy = NearestNeighborSort, typename MetricType = mlpack::metric::SquaredEuclideanDistance, typename TreeType = tree::BinarySpaceTree<bound::HRectBound<2>, QueryStat<SortPolicy> >>
class mlpack::neighbor::NeighborSearch< SortPolicy, MetricType, TreeType >

The NeighborSearch class is a template class for performing distance-based 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.

Template Parameters:
SortPolicyThe sort policy for distances; see NearestNeighborSort.
MetricTypeThe metric to use for computation.
TreeTypeThe tree type to use.

Definition at line 104 of file neighbor_search.hpp.


Constructor & Destructor Documentation

template<typename SortPolicy = NearestNeighborSort, typename MetricType = mlpack::metric::SquaredEuclideanDistance, typename TreeType = tree::BinarySpaceTree<bound::HRectBound<2>, QueryStat<SortPolicy> >>
mlpack::neighbor::NeighborSearch< SortPolicy, MetricType, TreeType >::NeighborSearch ( 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 NeighborSearch object, passing both a query and reference dataset.

Optionally, perform the computation in naive mode or single-tree mode, and set the leaf size used for tree-building. An initialized distance metric can be given, for cases where the metric has internal data (i.e. the distance::MahalanobisDistance class).

This method will copy the matrices to internal copies, which are rearranged during tree-building. You can avoid this extra copy by pre-constructing the trees and passing them using a diferent constructor.

Parameters:
referenceSetSet of reference points.
querySetSet of query points.
naiveIf true, O(n^2) naive search will be used (as opposed to dual-tree search). This overrides singleMode (if it is set to true).
singleModeIf true, single-tree search will be used (as opposed to dual-tree search).
leafSizeLeaf size for tree construction (ignored if tree is given).
metricAn optional instance of the MetricType class.
template<typename SortPolicy = NearestNeighborSort, typename MetricType = mlpack::metric::SquaredEuclideanDistance, typename TreeType = tree::BinarySpaceTree<bound::HRectBound<2>, QueryStat<SortPolicy> >>
mlpack::neighbor::NeighborSearch< SortPolicy, MetricType, TreeType >::NeighborSearch ( const typename TreeType::Mat &  referenceSet,
const bool  naive = false,
const bool  singleMode = false,
const size_t  leafSize = 20,
const MetricType  metric = MetricType() 
)

Initialize the NeighborSearch object, passing only one dataset, which is used as both the query and the reference dataset.

Optionally, perform the computation in naive mode or single-tree mode, and set the leaf size used for tree-building. An initialized distance metric can be given, for cases where the metric has internal data (i.e. the distance::MahalanobisDistance class).

If naive mode is being used and a pre-built tree is given, it may not work: naive mode operates by building a one-node tree (the root node holds all the points). If that condition is not satisfied with the pre-built tree, then naive mode will not work.

Parameters:
referenceSetSet of reference points.
naiveIf true, O(n^2) naive search will be used (as opposed to dual-tree search). This overrides singleMode (if it is set to true).
singleModeIf true, single-tree search will be used (as opposed to dual-tree search).
leafSizeLeaf size for tree construction (ignored if tree is given).
metricAn optional instance of the MetricType class.
template<typename SortPolicy = NearestNeighborSort, typename MetricType = mlpack::metric::SquaredEuclideanDistance, typename TreeType = tree::BinarySpaceTree<bound::HRectBound<2>, QueryStat<SortPolicy> >>
mlpack::neighbor::NeighborSearch< SortPolicy, MetricType, TreeType >::NeighborSearch ( TreeType *  referenceTree,
TreeType *  queryTree,
const typename TreeType::Mat &  referenceSet,
const typename TreeType::Mat &  querySet,
const bool  singleMode = false,
const MetricType  metric = MetricType() 
)

Initialize the NeighborSearch object with the given datasets and pre-constructed trees.

It is assumed that the points in referenceSet and querySet correspond to the points in referenceTree and queryTree, respectively. Optionally, choose to use single-tree mode. Naive mode is not available as an option for this constructor; instead, to run naive computation, construct a tree with all of the points in one leaf (i.e. leafSize = number of points). Additionally, an instantiated distance metric can be given, for cases where the distance metric holds data.

There is no copying of the data matrices in this constructor (because tree-building is not necessary), so this is the constructor to use when copies absolutely must be avoided.

Note:
Because tree-building (at least with BinarySpaceTree) modifies the ordering of a matrix, be sure you pass the modified matrix to this object! In addition, mapping the points of the matrix back to their original indices is not done when this constructor is used.
Parameters:
referenceTreePre-built tree for reference points.
queryTreePre-built tree for query points.
referenceSetSet of reference points corresponding to referenceTree.
querySetSet of query points corresponding to queryTree.
singleModeWhether single-tree computation should be used (as opposed to dual-tree computation).
metricInstantiated distance metric.
template<typename SortPolicy = NearestNeighborSort, typename MetricType = mlpack::metric::SquaredEuclideanDistance, typename TreeType = tree::BinarySpaceTree<bound::HRectBound<2>, QueryStat<SortPolicy> >>
mlpack::neighbor::NeighborSearch< SortPolicy, MetricType, TreeType >::NeighborSearch ( TreeType *  referenceTree,
const typename TreeType::Mat &  referenceSet,
const bool  singleMode = false,
const MetricType  metric = MetricType() 
)

Initialize the NeighborSearch object with the given reference dataset and pre-constructed tree.

It is assumed that the points in referenceSet correspond to the points in referenceTree. Optionally, choose to use single-tree mode. Naive mode is not available as an option for this constructor; instead, to run naive computation, construct a tree with all the points in one leaf (i.e. leafSize = number of points). Additionally, an instantiated distance metric can be given, for the case where the distance metric holds data.

There is no copying of the data matrices in this constructor (because tree-building is not necessary), so this is the constructor to use when copies absolutely must be avoided.

Note:
Because tree-building (at least with BinarySpaceTree) modifies the ordering of a matrix, be sure you pass the modified matrix to this object! In addition, mapping the points of the matrix back to their original indices is not done when this constructor is used.
Parameters:
referenceTreePre-built tree for reference points.
referenceSetSet of reference points corresponding to referenceTree.
singleModeWhether single-tree computation should be used (as opposed to dual-tree computation).
metricInstantiated distance metric.
template<typename SortPolicy = NearestNeighborSort, typename MetricType = mlpack::metric::SquaredEuclideanDistance, typename TreeType = tree::BinarySpaceTree<bound::HRectBound<2>, QueryStat<SortPolicy> >>
mlpack::neighbor::NeighborSearch< SortPolicy, MetricType, TreeType >::~NeighborSearch ( )

Delete the NeighborSearch object.

The tree is the only member we are responsible for deleting. The others will take care of themselves.


Member Function Documentation

template<typename SortPolicy = NearestNeighborSort, typename MetricType = mlpack::metric::SquaredEuclideanDistance, typename TreeType = tree::BinarySpaceTree<bound::HRectBound<2>, QueryStat<SortPolicy> >>
void mlpack::neighbor::NeighborSearch< SortPolicy, MetricType, TreeType >::Search ( const size_t  k,
arma::Mat< size_t > &  resultingNeighbors,
arma::mat &  distances 
)

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.

Parameters:
kNumber of neighbors to search for.
resultingNeighborsMatrix storing lists of neighbors for each query point.
distancesMatrix storing distances of neighbors for each query point.

Member Data Documentation

template<typename SortPolicy = NearestNeighborSort, typename MetricType = mlpack::metric::SquaredEuclideanDistance, typename TreeType = tree::BinarySpaceTree<bound::HRectBound<2>, QueryStat<SortPolicy> >>
MetricType mlpack::neighbor::NeighborSearch< SortPolicy, MetricType, TreeType >::metric [private]

Instantiation of kernel.

Definition at line 280 of file neighbor_search.hpp.

template<typename SortPolicy = NearestNeighborSort, typename MetricType = mlpack::metric::SquaredEuclideanDistance, typename TreeType = tree::BinarySpaceTree<bound::HRectBound<2>, QueryStat<SortPolicy> >>
bool mlpack::neighbor::NeighborSearch< SortPolicy, MetricType, TreeType >::naive [private]

Indicates if O(n^2) naive search is being used.

Definition at line 275 of file neighbor_search.hpp.

template<typename SortPolicy = NearestNeighborSort, typename MetricType = mlpack::metric::SquaredEuclideanDistance, typename TreeType = tree::BinarySpaceTree<bound::HRectBound<2>, QueryStat<SortPolicy> >>
size_t mlpack::neighbor::NeighborSearch< SortPolicy, MetricType, TreeType >::numberOfPrunes [private]

Total number of pruned nodes during the neighbor search.

Definition at line 288 of file neighbor_search.hpp.

template<typename SortPolicy = NearestNeighborSort, typename MetricType = mlpack::metric::SquaredEuclideanDistance, typename TreeType = tree::BinarySpaceTree<bound::HRectBound<2>, QueryStat<SortPolicy> >>
std::vector<size_t> mlpack::neighbor::NeighborSearch< SortPolicy, MetricType, TreeType >::oldFromNewQueries [private]

Permutations of query points during tree building.

Definition at line 285 of file neighbor_search.hpp.

template<typename SortPolicy = NearestNeighborSort, typename MetricType = mlpack::metric::SquaredEuclideanDistance, typename TreeType = tree::BinarySpaceTree<bound::HRectBound<2>, QueryStat<SortPolicy> >>
std::vector<size_t> mlpack::neighbor::NeighborSearch< SortPolicy, MetricType, TreeType >::oldFromNewReferences [private]

Permutations of reference points during tree building.

Definition at line 283 of file neighbor_search.hpp.

template<typename SortPolicy = NearestNeighborSort, typename MetricType = mlpack::metric::SquaredEuclideanDistance, typename TreeType = tree::BinarySpaceTree<bound::HRectBound<2>, QueryStat<SortPolicy> >>
bool mlpack::neighbor::NeighborSearch< SortPolicy, MetricType, TreeType >::ownQueryTree [private]

Indicates if we should free the query tree at deletion time.

Definition at line 272 of file neighbor_search.hpp.

template<typename SortPolicy = NearestNeighborSort, typename MetricType = mlpack::metric::SquaredEuclideanDistance, typename TreeType = tree::BinarySpaceTree<bound::HRectBound<2>, QueryStat<SortPolicy> >>
bool mlpack::neighbor::NeighborSearch< SortPolicy, MetricType, TreeType >::ownReferenceTree [private]

Indicates if we should free the reference tree at deletion time.

Definition at line 270 of file neighbor_search.hpp.

template<typename SortPolicy = NearestNeighborSort, typename MetricType = mlpack::metric::SquaredEuclideanDistance, typename TreeType = tree::BinarySpaceTree<bound::HRectBound<2>, QueryStat<SortPolicy> >>
arma::mat mlpack::neighbor::NeighborSearch< SortPolicy, MetricType, TreeType >::queryCopy [private]

Copy of query dataset (if we need it, because tree building modifies it).

Definition at line 257 of file neighbor_search.hpp.

template<typename SortPolicy = NearestNeighborSort, typename MetricType = mlpack::metric::SquaredEuclideanDistance, typename TreeType = tree::BinarySpaceTree<bound::HRectBound<2>, QueryStat<SortPolicy> >>
const arma::mat& mlpack::neighbor::NeighborSearch< SortPolicy, MetricType, TreeType >::querySet [private]

Query dataset (may not be given).

Definition at line 262 of file neighbor_search.hpp.

template<typename SortPolicy = NearestNeighborSort, typename MetricType = mlpack::metric::SquaredEuclideanDistance, typename TreeType = tree::BinarySpaceTree<bound::HRectBound<2>, QueryStat<SortPolicy> >>
TreeType* mlpack::neighbor::NeighborSearch< SortPolicy, MetricType, TreeType >::queryTree [private]

Pointer to the root of the query tree (might not exist).

Definition at line 267 of file neighbor_search.hpp.

template<typename SortPolicy = NearestNeighborSort, typename MetricType = mlpack::metric::SquaredEuclideanDistance, typename TreeType = tree::BinarySpaceTree<bound::HRectBound<2>, QueryStat<SortPolicy> >>
arma::mat mlpack::neighbor::NeighborSearch< SortPolicy, MetricType, TreeType >::referenceCopy [private]

Copy of reference dataset (if we need it, because tree building modifies it).

Definition at line 255 of file neighbor_search.hpp.

template<typename SortPolicy = NearestNeighborSort, typename MetricType = mlpack::metric::SquaredEuclideanDistance, typename TreeType = tree::BinarySpaceTree<bound::HRectBound<2>, QueryStat<SortPolicy> >>
const arma::mat& mlpack::neighbor::NeighborSearch< SortPolicy, MetricType, TreeType >::referenceSet [private]

Reference dataset.

Definition at line 260 of file neighbor_search.hpp.

template<typename SortPolicy = NearestNeighborSort, typename MetricType = mlpack::metric::SquaredEuclideanDistance, typename TreeType = tree::BinarySpaceTree<bound::HRectBound<2>, QueryStat<SortPolicy> >>
TreeType* mlpack::neighbor::NeighborSearch< SortPolicy, MetricType, TreeType >::referenceTree [private]

Pointer to the root of the reference tree.

Definition at line 265 of file neighbor_search.hpp.

template<typename SortPolicy = NearestNeighborSort, typename MetricType = mlpack::metric::SquaredEuclideanDistance, typename TreeType = tree::BinarySpaceTree<bound::HRectBound<2>, QueryStat<SortPolicy> >>
bool mlpack::neighbor::NeighborSearch< SortPolicy, MetricType, TreeType >::singleMode [private]

Indicates if single-tree search is being used (opposed to dual-tree).

Definition at line 277 of file neighbor_search.hpp.


The documentation for this class was generated from the following file: