MLPACK
1.0.4
|
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. | |
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. | |
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. | |
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. | |
~RangeSearch () | |
Destroy the RangeSearch object. | |
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. | |
Private Member Functions | |
void | ComputeBaseCase (const TreeType *referenceNode, const TreeType *queryNode, const math::Range &range, std::vector< std::vector< size_t > > &neighbors, std::vector< std::vector< double > > &distances) const |
Compute the base case, when both referenceNode and queryNode are leaves containing points. | |
void | DualTreeRecursion (const TreeType *referenceNode, const TreeType *queryNode, const math::Range &range, std::vector< std::vector< size_t > > &neighbors, std::vector< std::vector< double > > &distances) |
Perform the dual-tree recursion, which will recurse until the base case is necessary. | |
template<typename VecType > | |
void | SingleTreeRecursion (const TreeType *referenceNode, const VecType &queryPoint, const size_t queryIndex, const math::Range &range, std::vector< size_t > &neighbors, std::vector< double > &distances) |
Perform the single-tree recursion, which will recurse down the reference tree to get the results for a single point. | |
Private Attributes | |
MetricType | metric |
Instantiated distance metric. | |
bool | naive |
If true, O(n^2) naive computation is used. | |
size_t | numberOfPrunes |
The number of pruned nodes during computation. | |
std::vector< size_t > | oldFromNewQueries |
Mappings to old query indices (used when this object builds trees). | |
std::vector< size_t > | oldFromNewReferences |
Mappings to old reference indices (used when this object builds trees). | |
bool | ownQueryTree |
Indicates ownership of the query tree (meaning we need to delete it). | |
bool | ownReferenceTree |
Indicates ownership of the reference tree (meaning we need to delete it). | |
TreeType::Mat | queryCopy |
Copy of query matrix; used when a tree is built internally. | |
const TreeType::Mat & | querySet |
Query set (data should be accessed using this). | |
TreeType * | queryTree |
Query tree (may be NULL). | |
TreeType::Mat | referenceCopy |
Copy of reference matrix; used when a tree is built internally. | |
const TreeType::Mat & | referenceSet |
Reference set (data should be accessed using this). | |
TreeType * | referenceTree |
Reference tree. | |
bool | singleMode |
If true, single-tree computation is used. |
The RangeSearch class is a template class for performing range searches.
Definition at line 41 of file range_search.hpp.
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.
referenceSet | Reference dataset. |
querySet | Query dataset. |
naive | Whether the computation should be done in O(n^2) naive mode. |
singleMode | Whether single-tree computation should be used (as opposed to dual-tree computation). |
leafSize | The leaf size to be used during tree construction. |
metric | Instantiated distance metric. |
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.
referenceSet | Reference dataset. |
naive | Whether the computation should be done in O(n^2) naive mode. |
singleMode | Whether single-tree computation should be used (as opposed to dual-tree computation). |
leafSize | The leaf size to be used during tree construction. |
metric | Instantiated distance metric. |
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.
referenceTree | Pre-built tree for reference points. |
queryTree | Pre-built tree for query points. |
referenceSet | Set of reference points corresponding to referenceTree. |
querySet | Set of query points corresponding to queryTree. |
singleMode | Whether single-tree computation should be used (as opposed to dual-tree computation). |
metric | Instantiated distance metric. |
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.
referenceTree | Pre-built tree for reference points. |
referenceSet | Set of reference points corresponding to referenceTree. |
singleMode | Whether single-tree computation should be used (as opposed to dual-tree computation). |
metric | Instantiated distance metric. |
mlpack::range::RangeSearch< MetricType, TreeType >::~RangeSearch | ( | ) |
Destroy the RangeSearch object.
If trees were created, they will be deleted.
void mlpack::range::RangeSearch< MetricType, TreeType >::ComputeBaseCase | ( | const TreeType * | referenceNode, |
const TreeType * | queryNode, | ||
const math::Range & | range, | ||
std::vector< std::vector< size_t > > & | neighbors, | ||
std::vector< std::vector< double > > & | distances | ||
) | const [private] |
Compute the base case, when both referenceNode and queryNode are leaves containing points.
referenceNode | Reference node (must be a leaf). |
queryNode | Query node (must be a leaf). |
range | Range of distances to search for. |
neighbors | Object holding list of neighbors. |
distances | Object holding list of distances. |
void mlpack::range::RangeSearch< MetricType, TreeType >::DualTreeRecursion | ( | const TreeType * | referenceNode, |
const TreeType * | queryNode, | ||
const math::Range & | range, | ||
std::vector< std::vector< size_t > > & | neighbors, | ||
std::vector< std::vector< double > > & | distances | ||
) | [private] |
Perform the dual-tree recursion, which will recurse until the base case is necessary.
referenceNode | Reference node. |
queryNode | Query node. |
range | Range of distances to search for. |
neighbors | Object holding list of neighbors. |
distances | Object holding list of distances. |
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:
range | Range of distances in which to search. |
neighbors | Object which will hold the list of neighbors for each point which fell into the given range, for each query point. |
distances | Object which will hold the list of distances for each point which fell into the given range, for each query point. |
void mlpack::range::RangeSearch< MetricType, TreeType >::SingleTreeRecursion | ( | const TreeType * | referenceNode, |
const VecType & | queryPoint, | ||
const size_t | queryIndex, | ||
const math::Range & | range, | ||
std::vector< size_t > & | neighbors, | ||
std::vector< double > & | distances | ||
) | [private] |
Perform the single-tree recursion, which will recurse down the reference tree to get the results for a single point.
referenceNode | Reference node. |
queryPoint | Point to query for. |
queryIndex | Index of query node. |
range | Range of distances to search for. |
neighbors | Object holding list of neighbors. |
distances | Object holding list of distances. |
MetricType mlpack::range::RangeSearch< MetricType, TreeType >::metric [private] |
Instantiated distance metric.
Definition at line 282 of file range_search.hpp.
bool mlpack::range::RangeSearch< MetricType, TreeType >::naive [private] |
If true, O(n^2) naive computation is used.
Definition at line 277 of file range_search.hpp.
size_t mlpack::range::RangeSearch< MetricType, TreeType >::numberOfPrunes [private] |
The number of pruned nodes during computation.
Definition at line 285 of file range_search.hpp.
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 269 of file range_search.hpp.
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 267 of file range_search.hpp.
bool mlpack::range::RangeSearch< MetricType, TreeType >::ownQueryTree [private] |
Indicates ownership of the query tree (meaning we need to delete it).
Definition at line 274 of file range_search.hpp.
bool mlpack::range::RangeSearch< MetricType, TreeType >::ownReferenceTree [private] |
Indicates ownership of the reference tree (meaning we need to delete it).
Definition at line 272 of file range_search.hpp.
TreeType::Mat mlpack::range::RangeSearch< MetricType, TreeType >::queryCopy [private] |
Copy of query matrix; used when a tree is built internally.
Definition at line 254 of file range_search.hpp.
const TreeType::Mat& mlpack::range::RangeSearch< MetricType, TreeType >::querySet [private] |
Query set (data should be accessed using this).
Definition at line 259 of file range_search.hpp.
TreeType* mlpack::range::RangeSearch< MetricType, TreeType >::queryTree [private] |
Query tree (may be NULL).
Definition at line 264 of file range_search.hpp.
TreeType::Mat mlpack::range::RangeSearch< MetricType, TreeType >::referenceCopy [private] |
Copy of reference matrix; used when a tree is built internally.
Definition at line 252 of file range_search.hpp.
const TreeType::Mat& mlpack::range::RangeSearch< MetricType, TreeType >::referenceSet [private] |
Reference set (data should be accessed using this).
Definition at line 257 of file range_search.hpp.
TreeType* mlpack::range::RangeSearch< MetricType, TreeType >::referenceTree [private] |
Reference tree.
Definition at line 262 of file range_search.hpp.
bool mlpack::range::RangeSearch< MetricType, TreeType >::singleMode [private] |
If true, single-tree computation is used.
Definition at line 279 of file range_search.hpp.