mlpack_neighbor_RASearchRules (3)

Public Types

typedef

neighbor::NeighborSearchTraversalInfo

< TreeType > TraversalInfoType"

Public Member Functions

RASearchRules (const arma::mat &referenceSet, const arma::mat &querySet, arma::Mat< size_t > &neighbors, arma::mat &distances, MetricType &metric, const double tau=5, const double alpha=0.95, const bool naive=false, const bool sampleAtLeaves=false, const bool firstLeafExact=false, const size_t singleSampleLimit=20)

double BaseCase (const size_t queryIndex, const size_t referenceIndex)

size_t NumDistComputations ()

size_t NumEffectiveSamples ()

double Rescore (const size_t queryIndex, TreeType &referenceNode, const double oldScore)

Re-evaluate the score for recursion order. double Rescore (TreeType &queryNode, TreeType &referenceNode, const double oldScore)

Re-evaluate the score for recursion order. double Score (const size_t queryIndex, TreeType &referenceNode)

Get the score for recursion order. double Score (const size_t queryIndex, TreeType &referenceNode, const double baseCaseResult)

Get the score for recursion order. double Score (TreeType &queryNode, TreeType &referenceNode)

Get the score for recursion order. double Score (TreeType &queryNode, TreeType &referenceNode, const double baseCaseResult)

Get the score for recursion order, passing the base case result (in the situation where it may be needed to calculate the recursion order). const TraversalInfoType & TraversalInfo () const

TraversalInfoType & TraversalInfo ()

Private Member Functions

void InsertNeighbor (const size_t queryIndex, const size_t pos, const size_t neighbor, const double distance)

Insert a point into the neighbors and distances matrices; this is a helper function. size_t MinimumSamplesReqd (const size_t n, const size_t k, const double tau, const double alpha) const

Compute the minimum number of samples required to guarantee the given rank-approximation and success probability. void ObtainDistinctSamples (const size_t numSamples, const size_t rangeUpperBound, arma::uvec &distinctSamples) const

Pick up desired number of samples (with replacement) from a given range of integers so that only the distinct samples are returned from the range [0 - specified upper bound) double Score (const size_t queryIndex, TreeType &referenceNode, const double distance, const double bestDistance)

Perform actual scoring for single-tree case. double Score (TreeType &queryNode, TreeType &referenceNode, const double distance, const double bestDistance)

Perform actual scoring for dual-tree case. double SuccessProbability (const size_t n, const size_t k, const size_t m, const size_t t) const

Compute the success probability of obtaining 'k'-neighbors from a set of size 'n' within the top 't' neighbors if 'm' samples are made.

Private Attributes

arma::mat & distances

The matrix the resultant neighbor distances should be stored in. bool firstLeafExact

Whether to do exact computation on the first leaf before any sampling. MetricType & metric

The instantiated metric. arma::Mat< size_t > & neighbors

The matrix the resultant neighbor indices should be stored in. size_t numDistComputations

arma::Col< size_t > numSamplesMade

The number of samples made for every query. size_t numSamplesReqd

The minimum number of samples required per query. const arma::mat & querySet

The query set. const arma::mat & referenceSet

The reference set. bool sampleAtLeaves

Whether to sample at leaves or just use all of it. double samplingRatio

The sampling ratio. size_t singleSampleLimit

The limit on the largest node that can be approximated by sampling. TraversalInfoType traversalInfo

Friends

class RASearch< SortPolicy, MetricType, TreeType >

template<typename SortPolicy, typename MetricType, typename TreeType>class mlpack::neighbor::RASearchRules< SortPolicy, MetricType, TreeType >

Definition at line 34 of file ra_search_rules.hpp.

template<typename SortPolicy , typename MetricType , typename TreeType > typedef \fBneighbor::NeighborSearchTraversalInfo\fP<TreeType> \fBmlpack::neighbor::RASearchRules\fP< SortPolicy, MetricType, TreeType >::\fBTraversalInfoType\fP

Definition at line 205 of file ra_search_rules.hpp.

template<typename SortPolicy , typename MetricType , typename TreeType > \fBmlpack::neighbor::RASearchRules\fP< SortPolicy, MetricType, TreeType >::\fBRASearchRules\fP (const arma::mat &referenceSet, const arma::mat &querySet, arma::Mat< size_t > &neighbors, arma::mat &distances, MetricType &metric, const doubletau = \fC5\fP, const doublealpha = \fC0.95\fP, const boolnaive = \fCfalse\fP, const boolsampleAtLeaves = \fCfalse\fP, const boolfirstLeafExact = \fCfalse\fP, const size_tsingleSampleLimit = \fC20\fP)

template<typename SortPolicy , typename MetricType , typename TreeType > double \fBmlpack::neighbor::RASearchRules\fP< SortPolicy, MetricType, TreeType >::BaseCase (const size_tqueryIndex, const size_treferenceIndex)

template<typename SortPolicy , typename MetricType , typename TreeType > void \fBmlpack::neighbor::RASearchRules\fP< SortPolicy, MetricType, TreeType >::InsertNeighbor (const size_tqueryIndex, const size_tpos, const size_tneighbor, const doubledistance)\fC [private]\fP

Insert a point into the neighbors and distances matrices; this is a helper function.

Parameters:

queryIndex Index of point whose neighbors we are inserting into.

pos Position in list to insert into.

neighbor Index of reference point which is being inserted.

distance Distance from query point to reference point.

template<typename SortPolicy , typename MetricType , typename TreeType > size_t \fBmlpack::neighbor::RASearchRules\fP< SortPolicy, MetricType, TreeType >::MinimumSamplesReqd (const size_tn, const size_tk, const doubletau, const doublealpha) const\fC [private]\fP

Compute the minimum number of samples required to guarantee the given rank-approximation and success probability.

Parameters:

n Size of the set to be sampled from.

k The number of neighbors required within the rank-approximation.

tau The rank-approximation in percentile of the data.

alpha The success probability desired.

template<typename SortPolicy , typename MetricType , typename TreeType > size_t \fBmlpack::neighbor::RASearchRules\fP< SortPolicy, MetricType, TreeType >::NumDistComputations ()\fC [inline]\fP

Definition at line 196 of file ra_search_rules.hpp.

References mlpack::neighbor::RASearchRules< SortPolicy, MetricType, TreeType >::numDistComputations.

template<typename SortPolicy , typename MetricType , typename TreeType > size_t \fBmlpack::neighbor::RASearchRules\fP< SortPolicy, MetricType, TreeType >::NumEffectiveSamples ()\fC [inline]\fP

Definition at line 197 of file ra_search_rules.hpp.

References mlpack::neighbor::RASearchRules< SortPolicy, MetricType, TreeType >::numSamplesMade.

template<typename SortPolicy , typename MetricType , typename TreeType > void \fBmlpack::neighbor::RASearchRules\fP< SortPolicy, MetricType, TreeType >::ObtainDistinctSamples (const size_tnumSamples, const size_trangeUpperBound, arma::uvec &distinctSamples) const\fC [private]\fP

Pick up desired number of samples (with replacement) from a given range of integers so that only the distinct samples are returned from the range [0 - specified upper bound)

Parameters:

numSamples Number of random samples.

rangeUpperBound The upper bound on the range of integers.

distinctSamples The list of the distinct samples.

template<typename SortPolicy , typename MetricType , typename TreeType > double \fBmlpack::neighbor::RASearchRules\fP< SortPolicy, MetricType, TreeType >::Rescore (const size_tqueryIndex, TreeType &referenceNode, const doubleoldScore)

Re-evaluate the score for recursion order. A low score indicates priority for recursion, while DBL_MAX indicates that the node should not be recursed into at all (it should be pruned). This is used when the score has already been calculated, but another recursion may have modified the bounds for pruning. So the old score is checked against the new pruning bound.

For rank-approximation, it also checks if the number of samples left for a query to satisfy the rank constraint is small enough at this point of the algorithm, then this node is approximated by sampling and given a new score of 'DBL_MAX'.

Parameters:

queryIndex Index of query point.

referenceNode Candidate node to be recursed into.

oldScore Old score produced by Score() (or Rescore()).

template<typename SortPolicy , typename MetricType , typename TreeType > double \fBmlpack::neighbor::RASearchRules\fP< SortPolicy, MetricType, TreeType >::Rescore (TreeType &queryNode, TreeType &referenceNode, const doubleoldScore)

Re-evaluate the score for recursion order. A low score indicates priority for recursion, while DBL_MAX indicates that the node should not be recursed into at all (it should be pruned). This is used when the score has already been calculated, but another recursion may have modified the bounds for pruning. So the old score is checked against the new pruning bound.

For the rank-approximation, we check if the referenceNode can be approximated by sampling. If it can be, enough samples are made for every query in the queryNode. No further query-tree traversal is performed.

The 'NumSamplesMade' query stat is propagated up the tree. And then if pruning occurs (by distance or by sampling), the 'NumSamplesMade' stat is not propagated down the tree. If no pruning occurs, the stat is propagated down the tree.

Parameters:

queryNode Candidate query node to recurse into.

referenceNode Candidate reference node to recurse into.

oldScore Old score produced by Socre() (or Rescore()).

template<typename SortPolicy , typename MetricType , typename TreeType > double \fBmlpack::neighbor::RASearchRules\fP< SortPolicy, MetricType, TreeType >::Score (const size_tqueryIndex, TreeType &referenceNode)

Get the score for recursion order. A low score indicates priority for recursion, while DBL_MAX indicates that the node should not be recursed into at all (it should be pruned).

For rank-approximation, the scoring function first checks if pruning by distance is possible. If yes, then the node is given the score of 'DBL_MAX' and the expected number of samples from that node are added to the number of samples made for the query.

If no, then the function tries to see if the node can be pruned by approximation. If number of samples required from this node is small enough, then that number of samples are acquired from this node and the score is set to be 'DBL_MAX'.

If the pruning by approximation is not possible either, the algorithm continues with the usual tree-traversal.

Parameters:

queryIndex Index of query point.

referenceNode Candidate node to be recursed into.

template<typename SortPolicy , typename MetricType , typename TreeType > double \fBmlpack::neighbor::RASearchRules\fP< SortPolicy, MetricType, TreeType >::Score (const size_tqueryIndex, TreeType &referenceNode, const doublebaseCaseResult)

Get the score for recursion order. A low score indicates priority for recursion, while DBL_MAX indicates that the node should not be recursed into at all (it should be pruned).

For rank-approximation, the scoring function first checks if pruning by distance is possible. If yes, then the node is given the score of 'DBL_MAX' and the expected number of samples from that node are added to the number of samples made for the query.

If no, then the function tries to see if the node can be pruned by approximation. If number of samples required from this node is small enough, then that number of samples are acquired from this node and the score is set to be 'DBL_MAX'.

If the pruning by approximation is not possible either, the algorithm continues with the usual tree-traversal.

Parameters:

queryIndex Index of query point.

referenceNode Candidate node to be recursed into.

baseCaseResult Result of BaseCase(queryIndex, referenceNode).

template<typename SortPolicy , typename MetricType , typename TreeType > double \fBmlpack::neighbor::RASearchRules\fP< SortPolicy, MetricType, TreeType >::Score (TreeType &queryNode, TreeType &referenceNode)

Get the score for recursion order. A low score indicates priority for recursionm while DBL_MAX indicates that the node should not be recursed into at all (it should be pruned).

For the rank-approximation, we check if the referenceNode can be approximated by sampling. If it can be, enough samples are made for every query in the queryNode. No further query-tree traversal is performed.

The 'NumSamplesMade' query stat is propagated up the tree. And then if pruning occurs (by distance or by sampling), the 'NumSamplesMade' stat is not propagated down the tree. If no pruning occurs, the stat is propagated down the tree.

Parameters:

queryNode Candidate query node to recurse into.

referenceNode Candidate reference node to recurse into.

template<typename SortPolicy , typename MetricType , typename TreeType > double \fBmlpack::neighbor::RASearchRules\fP< SortPolicy, MetricType, TreeType >::Score (TreeType &queryNode, TreeType &referenceNode, const doublebaseCaseResult)

Get the score for recursion order, passing the base case result (in the situation where it may be needed to calculate the recursion order). A low score indicates priority for recursion, while DBL_MAX indicates that the node should not be recursed into at all (it should be pruned).

For the rank-approximation, we check if the referenceNode can be approximated by sampling. If it can be, enough samples are made for every query in the queryNode. No further query-tree traversal is performed.

The 'NumSamplesMade' query stat is propagated up the tree. And then if pruning occurs (by distance or by sampling), the 'NumSamplesMade' stat is not propagated down the tree. If no pruning occurs, the stat is propagated down the tree.

Parameters:

queryNode Candidate query node to recurse into.

referenceNode Candidate reference node to recurse into.

baseCaseResult Result of BaseCase(queryIndex, referenceNode).

template<typename SortPolicy , typename MetricType , typename TreeType > double \fBmlpack::neighbor::RASearchRules\fP< SortPolicy, MetricType, TreeType >::Score (const size_tqueryIndex, TreeType &referenceNode, const doubledistance, const doublebestDistance)\fC [private]\fP

Perform actual scoring for single-tree case.

template<typename SortPolicy , typename MetricType , typename TreeType > double \fBmlpack::neighbor::RASearchRules\fP< SortPolicy, MetricType, TreeType >::Score (TreeType &queryNode, TreeType &referenceNode, const doubledistance, const doublebestDistance)\fC [private]\fP

Perform actual scoring for dual-tree case.

template<typename SortPolicy , typename MetricType , typename TreeType > double \fBmlpack::neighbor::RASearchRules\fP< SortPolicy, MetricType, TreeType >::SuccessProbability (const size_tn, const size_tk, const size_tm, const size_tt) const\fC [private]\fP

Compute the success probability of obtaining 'k'-neighbors from a set of size 'n' within the top 't' neighbors if 'm' samples are made.

Parameters:

n Size of the set being sampled from.

k The number of neighbors required within the rank-approximation.

m The number of random samples.

t The desired rank-approximation.

template<typename SortPolicy , typename MetricType , typename TreeType > const \fBTraversalInfoType\fP& \fBmlpack::neighbor::RASearchRules\fP< SortPolicy, MetricType, TreeType >::\fBTraversalInfo\fP () const\fC [inline]\fP

Definition at line 207 of file ra_search_rules.hpp.

References mlpack::neighbor::RASearchRules< SortPolicy, MetricType, TreeType >::traversalInfo.

template<typename SortPolicy , typename MetricType , typename TreeType > \fBTraversalInfoType\fP& \fBmlpack::neighbor::RASearchRules\fP< SortPolicy, MetricType, TreeType >::\fBTraversalInfo\fP ()\fC [inline]\fP

Definition at line 208 of file ra_search_rules.hpp.

References mlpack::neighbor::RASearchRules< SortPolicy, MetricType, TreeType >::traversalInfo.

template<typename SortPolicy , typename MetricType , typename TreeType > friend class \fBRASearch\fP< SortPolicy, MetricType, TreeType >\fC [friend]\fP

Definition at line 323 of file ra_search_rules.hpp.

template<typename SortPolicy , typename MetricType , typename TreeType > arma::mat& \fBmlpack::neighbor::RASearchRules\fP< SortPolicy, MetricType, TreeType >::distances\fC [private]\fP

The matrix the resultant neighbor distances should be stored in.

Definition at line 221 of file ra_search_rules.hpp.

template<typename SortPolicy , typename MetricType , typename TreeType > bool \fBmlpack::neighbor::RASearchRules\fP< SortPolicy, MetricType, TreeType >::firstLeafExact\fC [private]\fP

Whether to do exact computation on the first leaf before any sampling.

Definition at line 230 of file ra_search_rules.hpp.

template<typename SortPolicy , typename MetricType , typename TreeType > MetricType& \fBmlpack::neighbor::RASearchRules\fP< SortPolicy, MetricType, TreeType >::metric\fC [private]\fP

The instantiated metric.

Definition at line 224 of file ra_search_rules.hpp.

template<typename SortPolicy , typename MetricType , typename TreeType > arma::Mat<size_t>& \fBmlpack::neighbor::RASearchRules\fP< SortPolicy, MetricType, TreeType >::neighbors\fC [private]\fP

The matrix the resultant neighbor indices should be stored in.

Definition at line 218 of file ra_search_rules.hpp.

template<typename SortPolicy , typename MetricType , typename TreeType > size_t \fBmlpack::neighbor::RASearchRules\fP< SortPolicy, MetricType, TreeType >::numDistComputations\fC [private]\fP

Definition at line 245 of file ra_search_rules.hpp.

Referenced by mlpack::neighbor::RASearchRules< SortPolicy, MetricType, TreeType >::NumDistComputations().

template<typename SortPolicy , typename MetricType , typename TreeType > arma::Col<size_t> \fBmlpack::neighbor::RASearchRules\fP< SortPolicy, MetricType, TreeType >::numSamplesMade\fC [private]\fP

The number of samples made for every query.

Definition at line 239 of file ra_search_rules.hpp.

Referenced by mlpack::neighbor::RASearchRules< SortPolicy, MetricType, TreeType >::NumEffectiveSamples().

template<typename SortPolicy , typename MetricType , typename TreeType > size_t \fBmlpack::neighbor::RASearchRules\fP< SortPolicy, MetricType, TreeType >::numSamplesReqd\fC [private]\fP

The minimum number of samples required per query.

Definition at line 236 of file ra_search_rules.hpp.

template<typename SortPolicy , typename MetricType , typename TreeType > const arma::mat& \fBmlpack::neighbor::RASearchRules\fP< SortPolicy, MetricType, TreeType >::querySet\fC [private]\fP

The query set.

Definition at line 215 of file ra_search_rules.hpp.

template<typename SortPolicy , typename MetricType , typename TreeType > const arma::mat& \fBmlpack::neighbor::RASearchRules\fP< SortPolicy, MetricType, TreeType >::referenceSet\fC [private]\fP

The reference set.

Definition at line 212 of file ra_search_rules.hpp.

template<typename SortPolicy , typename MetricType , typename TreeType > bool \fBmlpack::neighbor::RASearchRules\fP< SortPolicy, MetricType, TreeType >::sampleAtLeaves\fC [private]\fP

Whether to sample at leaves or just use all of it.

Definition at line 227 of file ra_search_rules.hpp.

template<typename SortPolicy , typename MetricType , typename TreeType > double \fBmlpack::neighbor::RASearchRules\fP< SortPolicy, MetricType, TreeType >::samplingRatio\fC [private]\fP

The sampling ratio.

Definition at line 242 of file ra_search_rules.hpp.

template<typename SortPolicy , typename MetricType , typename TreeType > size_t \fBmlpack::neighbor::RASearchRules\fP< SortPolicy, MetricType, TreeType >::singleSampleLimit\fC [private]\fP

The limit on the largest node that can be approximated by sampling.

Definition at line 233 of file ra_search_rules.hpp.

template<typename SortPolicy , typename MetricType , typename TreeType > \fBTraversalInfoType\fP \fBmlpack::neighbor::RASearchRules\fP< SortPolicy, MetricType, TreeType >::traversalInfo\fC [private]\fP

Definition at line 247 of file ra_search_rules.hpp.

Referenced by mlpack::neighbor::RASearchRules< SortPolicy, MetricType, TreeType >::TraversalInfo().

Generated automatically by Doxygen for MLPACK from the source code.