MLPACK  1.0.7
Public Member Functions | Private Attributes | List of all members
mlpack::range::RangeSearch< MetricType, TreeType > Class Template Reference

The RangeSearch class is a template class for performing range searches. More...

Public Member Functions

 RangeSearch (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 RangeSearch object with a different reference set and a query set. More...
 
 RangeSearch (const typename TreeType::Mat &referenceSet, const bool naive=false, const bool singleMode=false, const size_t leafSize=20, const MetricType metric=MetricType())
 Initialize the RangeSearch object with only a reference set, which will also be used as a query set. More...
 
 RangeSearch (TreeType *referenceTree, TreeType *queryTree, const typename TreeType::Mat &referenceSet, const typename TreeType::Mat &querySet, const bool singleMode=false, const MetricType metric=MetricType())
 Initialize the RangeSearch object with the given datasets and pre-constructed trees. More...
 
 RangeSearch (TreeType *referenceTree, const typename TreeType::Mat &referenceSet, const bool singleMode=false, const MetricType metric=MetricType())
 Initialize the RangeSearch object with the given reference dataset and pre-constructed tree. More...
 
 ~RangeSearch ()
 Destroy the RangeSearch object. More...
 
void Search (const math::Range &range, std::vector< std::vector< size_t > > &neighbors, std::vector< std::vector< double > > &distances)
 Search for all points in the given range, returning the results in the neighbors and distances objects. More...
 

Private Attributes

bool hasQuerySet
 If true, a query set was passed; if false, the query set is the reference set. More...
 
MetricType metric
 Instantiated distance metric. More...
 
bool naive
 If true, O(n^2) naive computation is used. More...
 
size_t numPrunes
 The number of pruned nodes during computation. More...
 
std::vector< size_t > oldFromNewQueries
 Mappings to old query indices (used when this object builds trees). More...
 
std::vector< size_t > oldFromNewReferences
 Mappings to old reference indices (used when this object builds trees). More...
 
TreeType::Mat queryCopy
 Copy of query matrix; used when a tree is built internally. More...
 
const TreeType::Mat & querySet
 Query set (data should be accessed using this). More...
 
TreeType * queryTree
 Query tree (may be NULL). More...
 
TreeType::Mat referenceCopy
 Copy of reference matrix; used when a tree is built internally. More...
 
const TreeType::Mat & referenceSet
 Reference set (data should be accessed using this). More...
 
TreeType * referenceTree
 Reference tree. More...
 
bool singleMode
 If true, single-tree computation is used. More...
 
bool treeOwner
 If true, this object is responsible for deleting the trees. More...
 

Detailed Description

template<typename MetricType = mlpack::metric::EuclideanDistance, typename TreeType = tree::BinarySpaceTree<bound::HRectBound<2>, RangeSearchStat>>
class mlpack::range::RangeSearch< MetricType, TreeType >

The RangeSearch class is a template class for performing range searches.

It is implemented in the style of a generalized tree-independent dual-tree algorithm; for more details on the actual algorithm, see the RangeSearchRules class.

Definition at line 46 of file range_search.hpp.

Constructor & Destructor Documentation

template<typename MetricType = mlpack::metric::EuclideanDistance, typename TreeType = tree::BinarySpaceTree<bound::HRectBound<2>, RangeSearchStat>>
mlpack::range::RangeSearch< MetricType, TreeType >::RangeSearch ( 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 RangeSearch object with a different reference set and a query set.

Optionally, perform the computation in naive mode or single-tree mode, and set the leaf size used for tree-building. Additionally, an instantiated metric can be given, for cases where the distance metric holds data.

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 different constructor.

Parameters
referenceSetReference dataset.
querySetQuery dataset.
naiveWhether the computation should be done in O(n^2) naive mode.
singleModeWhether single-tree computation should be used (as opposed to dual-tree computation).
leafSizeThe leaf size to be used during tree construction.
metricInstantiated distance metric.
template<typename MetricType = mlpack::metric::EuclideanDistance, typename TreeType = tree::BinarySpaceTree<bound::HRectBound<2>, RangeSearchStat>>
mlpack::range::RangeSearch< MetricType, TreeType >::RangeSearch ( const typename TreeType::Mat &  referenceSet,
const bool  naive = false,
const bool  singleMode = false,
const size_t  leafSize = 20,
const MetricType  metric = MetricType() 
)

Initialize the RangeSearch object with only a reference set, which will also be used as a query set.

Optionally, perform the computation in naive mode or single-tree mode, and set the leaf size used for tree-building. Additionally an instantiated metric can be given, for cases where the distance metric holds data.

This method will copy the reference matrix to an internal copy, which is rearranged during tree-building. You can avoid this extra copy by pre-constructing the reference tree and passing it using a different constructor.

Parameters
referenceSetReference dataset.
naiveWhether the computation should be done in O(n^2) naive mode.
singleModeWhether single-tree computation should be used (as opposed to dual-tree computation).
leafSizeThe leaf size to be used during tree construction.
metricInstantiated distance metric.
template<typename MetricType = mlpack::metric::EuclideanDistance, typename TreeType = tree::BinarySpaceTree<bound::HRectBound<2>, RangeSearchStat>>
mlpack::range::RangeSearch< MetricType, TreeType >::RangeSearch ( TreeType *  referenceTree,
TreeType *  queryTree,
const typename TreeType::Mat &  referenceSet,
const typename TreeType::Mat &  querySet,
const bool  singleMode = false,
const MetricType  metric = MetricType() 
)

Initialize the RangeSearch 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 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 MetricType = mlpack::metric::EuclideanDistance, typename TreeType = tree::BinarySpaceTree<bound::HRectBound<2>, RangeSearchStat>>
mlpack::range::RangeSearch< MetricType, TreeType >::RangeSearch ( TreeType *  referenceTree,
const typename TreeType::Mat &  referenceSet,
const bool  singleMode = false,
const MetricType  metric = MetricType() 
)

Initialize the RangeSearch 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 MetricType = mlpack::metric::EuclideanDistance, typename TreeType = tree::BinarySpaceTree<bound::HRectBound<2>, RangeSearchStat>>
mlpack::range::RangeSearch< MetricType, TreeType >::~RangeSearch ( )

Destroy the RangeSearch object.

If trees were created, they will be deleted.

Member Function Documentation

template<typename MetricType = mlpack::metric::EuclideanDistance, typename TreeType = tree::BinarySpaceTree<bound::HRectBound<2>, RangeSearchStat>>
void mlpack::range::RangeSearch< MetricType, TreeType >::Search ( const math::Range range,
std::vector< std::vector< size_t > > &  neighbors,
std::vector< std::vector< double > > &  distances 
)

Search for all points in the given range, returning the results in the neighbors and distances objects.

Each entry in the external vector corresponds to a query point. Each of these entries holds a vector which contains the indices and distances of the reference points falling into the given range.

That is:

  • neighbors.size() and distances.size() both equal the number of query points.
  • neighbors[i] contains the indices of all the points in the reference set which have distances inside the given range to query point i.
  • distances[i] contains all of the distances corresponding to the indices contained in neighbors[i].
  • neighbors[i] and distances[i] are not sorted in any particular order.
Parameters
rangeRange of distances in which to search.
neighborsObject which will hold the list of neighbors for each point which fell into the given range, for each query point.
distancesObject which will hold the list of distances for each point which fell into the given range, for each query point.

Member Data Documentation

template<typename MetricType = mlpack::metric::EuclideanDistance, typename TreeType = tree::BinarySpaceTree<bound::HRectBound<2>, RangeSearchStat>>
bool mlpack::range::RangeSearch< MetricType, TreeType >::hasQuerySet
private

If true, a query set was passed; if false, the query set is the reference set.

Definition at line 229 of file range_search.hpp.

template<typename MetricType = mlpack::metric::EuclideanDistance, typename TreeType = tree::BinarySpaceTree<bound::HRectBound<2>, RangeSearchStat>>
MetricType mlpack::range::RangeSearch< MetricType, TreeType >::metric
private

Instantiated distance metric.

Definition at line 237 of file range_search.hpp.

template<typename MetricType = mlpack::metric::EuclideanDistance, typename TreeType = tree::BinarySpaceTree<bound::HRectBound<2>, RangeSearchStat>>
bool mlpack::range::RangeSearch< MetricType, TreeType >::naive
private

If true, O(n^2) naive computation is used.

Definition at line 232 of file range_search.hpp.

template<typename MetricType = mlpack::metric::EuclideanDistance, typename TreeType = tree::BinarySpaceTree<bound::HRectBound<2>, RangeSearchStat>>
size_t mlpack::range::RangeSearch< MetricType, TreeType >::numPrunes
private

The number of pruned nodes during computation.

Definition at line 240 of file range_search.hpp.

template<typename MetricType = mlpack::metric::EuclideanDistance, typename TreeType = tree::BinarySpaceTree<bound::HRectBound<2>, RangeSearchStat>>
std::vector<size_t> mlpack::range::RangeSearch< MetricType, TreeType >::oldFromNewQueries
private

Mappings to old query indices (used when this object builds trees).

Definition at line 223 of file range_search.hpp.

template<typename MetricType = mlpack::metric::EuclideanDistance, typename TreeType = tree::BinarySpaceTree<bound::HRectBound<2>, RangeSearchStat>>
std::vector<size_t> mlpack::range::RangeSearch< MetricType, TreeType >::oldFromNewReferences
private

Mappings to old reference indices (used when this object builds trees).

Definition at line 221 of file range_search.hpp.

template<typename MetricType = mlpack::metric::EuclideanDistance, typename TreeType = tree::BinarySpaceTree<bound::HRectBound<2>, RangeSearchStat>>
TreeType::Mat mlpack::range::RangeSearch< MetricType, TreeType >::queryCopy
private

Copy of query matrix; used when a tree is built internally.

Definition at line 208 of file range_search.hpp.

template<typename MetricType = mlpack::metric::EuclideanDistance, typename TreeType = tree::BinarySpaceTree<bound::HRectBound<2>, RangeSearchStat>>
const TreeType::Mat& mlpack::range::RangeSearch< MetricType, TreeType >::querySet
private

Query set (data should be accessed using this).

Definition at line 213 of file range_search.hpp.

template<typename MetricType = mlpack::metric::EuclideanDistance, typename TreeType = tree::BinarySpaceTree<bound::HRectBound<2>, RangeSearchStat>>
TreeType* mlpack::range::RangeSearch< MetricType, TreeType >::queryTree
private

Query tree (may be NULL).

Definition at line 218 of file range_search.hpp.

template<typename MetricType = mlpack::metric::EuclideanDistance, typename TreeType = tree::BinarySpaceTree<bound::HRectBound<2>, RangeSearchStat>>
TreeType::Mat mlpack::range::RangeSearch< MetricType, TreeType >::referenceCopy
private

Copy of reference matrix; used when a tree is built internally.

Definition at line 206 of file range_search.hpp.

template<typename MetricType = mlpack::metric::EuclideanDistance, typename TreeType = tree::BinarySpaceTree<bound::HRectBound<2>, RangeSearchStat>>
const TreeType::Mat& mlpack::range::RangeSearch< MetricType, TreeType >::referenceSet
private

Reference set (data should be accessed using this).

Definition at line 211 of file range_search.hpp.

template<typename MetricType = mlpack::metric::EuclideanDistance, typename TreeType = tree::BinarySpaceTree<bound::HRectBound<2>, RangeSearchStat>>
TreeType* mlpack::range::RangeSearch< MetricType, TreeType >::referenceTree
private

Reference tree.

Definition at line 216 of file range_search.hpp.

template<typename MetricType = mlpack::metric::EuclideanDistance, typename TreeType = tree::BinarySpaceTree<bound::HRectBound<2>, RangeSearchStat>>
bool mlpack::range::RangeSearch< MetricType, TreeType >::singleMode
private

If true, single-tree computation is used.

Definition at line 234 of file range_search.hpp.

template<typename MetricType = mlpack::metric::EuclideanDistance, typename TreeType = tree::BinarySpaceTree<bound::HRectBound<2>, RangeSearchStat>>
bool mlpack::range::RangeSearch< MetricType, TreeType >::treeOwner
private

If true, this object is responsible for deleting the trees.

Definition at line 226 of file range_search.hpp.


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