mlpack  1.0.12
Public Types | Public Member Functions | Private Member Functions | Private Attributes | Friends | List of all members
mlpack::neighbor::RASearchRules< SortPolicy, MetricType, TreeType > Class Template Reference

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. More...
 
double Rescore (TreeType &queryNode, TreeType &referenceNode, const double oldScore)
 Re-evaluate the score for recursion order. More...
 
double Score (const size_t queryIndex, TreeType &referenceNode)
 Get the score for recursion order. More...
 
double Score (const size_t queryIndex, TreeType &referenceNode, const double baseCaseResult)
 Get the score for recursion order. More...
 
double Score (TreeType &queryNode, TreeType &referenceNode)
 Get the score for recursion order. More...
 
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). More...
 
const TraversalInfoTypeTraversalInfo () const
 
TraversalInfoTypeTraversalInfo ()
 

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. More...
 
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. More...
 
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) More...
 
double Score (const size_t queryIndex, TreeType &referenceNode, const double distance, const double bestDistance)
 Perform actual scoring for single-tree case. More...
 
double Score (TreeType &queryNode, TreeType &referenceNode, const double distance, const double bestDistance)
 Perform actual scoring for dual-tree case. More...
 
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. More...
 

Private Attributes

arma::mat & distances
 The matrix the resultant neighbor distances should be stored in. More...
 
bool firstLeafExact
 Whether to do exact computation on the first leaf before any sampling. More...
 
MetricType & metric
 The instantiated metric. More...
 
arma::Mat< size_t > & neighbors
 The matrix the resultant neighbor indices should be stored in. More...
 
size_t numDistComputations
 
arma::Col< size_t > numSamplesMade
 The number of samples made for every query. More...
 
size_t numSamplesReqd
 The minimum number of samples required per query. More...
 
const arma::mat & querySet
 The query set. More...
 
const arma::mat & referenceSet
 The reference set. More...
 
bool sampleAtLeaves
 Whether to sample at leaves or just use all of it. More...
 
double samplingRatio
 The sampling ratio. More...
 
size_t singleSampleLimit
 The limit on the largest node that can be approximated by sampling. More...
 
TraversalInfoType traversalInfo
 

Friends

class RASearch< SortPolicy, MetricType, TreeType >
 

Detailed Description

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

Definition at line 26 of file ra_search_rules.hpp.

Member Typedef Documentation

template<typename SortPolicy , typename MetricType , typename TreeType >
typedef neighbor::NeighborSearchTraversalInfo<TreeType> mlpack::neighbor::RASearchRules< SortPolicy, MetricType, TreeType >::TraversalInfoType

Definition at line 197 of file ra_search_rules.hpp.

Constructor & Destructor Documentation

template<typename SortPolicy , typename MetricType , typename TreeType >
mlpack::neighbor::RASearchRules< SortPolicy, MetricType, TreeType >::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 
)

Member Function Documentation

template<typename SortPolicy , typename MetricType , typename TreeType >
double mlpack::neighbor::RASearchRules< SortPolicy, MetricType, TreeType >::BaseCase ( const size_t  queryIndex,
const size_t  referenceIndex 
)
template<typename SortPolicy , typename MetricType , typename TreeType >
void mlpack::neighbor::RASearchRules< SortPolicy, MetricType, TreeType >::InsertNeighbor ( const size_t  queryIndex,
const size_t  pos,
const size_t  neighbor,
const double  distance 
)
private

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

Parameters
queryIndexIndex of point whose neighbors we are inserting into.
posPosition in list to insert into.
neighborIndex of reference point which is being inserted.
distanceDistance from query point to reference point.
template<typename SortPolicy , typename MetricType , typename TreeType >
size_t mlpack::neighbor::RASearchRules< SortPolicy, MetricType, TreeType >::MinimumSamplesReqd ( const size_t  n,
const size_t  k,
const double  tau,
const double  alpha 
) const
private

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

Parameters
nSize of the set to be sampled from.
kThe number of neighbors required within the rank-approximation.
tauThe rank-approximation in percentile of the data.
alphaThe success probability desired.
template<typename SortPolicy , typename MetricType , typename TreeType >
size_t mlpack::neighbor::RASearchRules< SortPolicy, MetricType, TreeType >::NumDistComputations ( )
inline
template<typename SortPolicy , typename MetricType , typename TreeType >
size_t mlpack::neighbor::RASearchRules< SortPolicy, MetricType, TreeType >::NumEffectiveSamples ( )
inline
template<typename SortPolicy , typename MetricType , typename TreeType >
void mlpack::neighbor::RASearchRules< SortPolicy, MetricType, TreeType >::ObtainDistinctSamples ( const size_t  numSamples,
const size_t  rangeUpperBound,
arma::uvec &  distinctSamples 
) const
private

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
numSamplesNumber of random samples.
rangeUpperBoundThe upper bound on the range of integers.
distinctSamplesThe list of the distinct samples.
template<typename SortPolicy , typename MetricType , typename TreeType >
double mlpack::neighbor::RASearchRules< SortPolicy, MetricType, TreeType >::Rescore ( const size_t  queryIndex,
TreeType &  referenceNode,
const double  oldScore 
)

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
queryIndexIndex of query point.
referenceNodeCandidate node to be recursed into.
oldScoreOld score produced by Score() (or Rescore()).
template<typename SortPolicy , typename MetricType , typename TreeType >
double mlpack::neighbor::RASearchRules< SortPolicy, MetricType, TreeType >::Rescore ( TreeType &  queryNode,
TreeType &  referenceNode,
const double  oldScore 
)

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
queryNodeCandidate query node to recurse into.
referenceNodeCandidate reference node to recurse into.
oldScoreOld score produced by Socre() (or Rescore()).
template<typename SortPolicy , typename MetricType , typename TreeType >
double mlpack::neighbor::RASearchRules< SortPolicy, MetricType, TreeType >::Score ( const size_t  queryIndex,
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
queryIndexIndex of query point.
referenceNodeCandidate node to be recursed into.
template<typename SortPolicy , typename MetricType , typename TreeType >
double mlpack::neighbor::RASearchRules< SortPolicy, MetricType, TreeType >::Score ( const size_t  queryIndex,
TreeType &  referenceNode,
const double  baseCaseResult 
)

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
queryIndexIndex of query point.
referenceNodeCandidate node to be recursed into.
baseCaseResultResult of BaseCase(queryIndex, referenceNode).
template<typename SortPolicy , typename MetricType , typename TreeType >
double mlpack::neighbor::RASearchRules< 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
queryNodeCandidate query node to recurse into.
referenceNodeCandidate reference node to recurse into.
template<typename SortPolicy , typename MetricType , typename TreeType >
double mlpack::neighbor::RASearchRules< SortPolicy, MetricType, TreeType >::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).

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
queryNodeCandidate query node to recurse into.
referenceNodeCandidate reference node to recurse into.
baseCaseResultResult of BaseCase(queryIndex, referenceNode).
template<typename SortPolicy , typename MetricType , typename TreeType >
double mlpack::neighbor::RASearchRules< SortPolicy, MetricType, TreeType >::Score ( const size_t  queryIndex,
TreeType &  referenceNode,
const double  distance,
const double  bestDistance 
)
private

Perform actual scoring for single-tree case.

template<typename SortPolicy , typename MetricType , typename TreeType >
double mlpack::neighbor::RASearchRules< SortPolicy, MetricType, TreeType >::Score ( TreeType &  queryNode,
TreeType &  referenceNode,
const double  distance,
const double  bestDistance 
)
private

Perform actual scoring for dual-tree case.

template<typename SortPolicy , typename MetricType , typename TreeType >
double mlpack::neighbor::RASearchRules< SortPolicy, MetricType, TreeType >::SuccessProbability ( const size_t  n,
const size_t  k,
const size_t  m,
const size_t  t 
) const
private

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
nSize of the set being sampled from.
kThe number of neighbors required within the rank-approximation.
mThe number of random samples.
tThe desired rank-approximation.
template<typename SortPolicy , typename MetricType , typename TreeType >
const TraversalInfoType& mlpack::neighbor::RASearchRules< SortPolicy, MetricType, TreeType >::TraversalInfo ( ) const
inline
template<typename SortPolicy , typename MetricType , typename TreeType >
TraversalInfoType& mlpack::neighbor::RASearchRules< SortPolicy, MetricType, TreeType >::TraversalInfo ( )
inline

Friends And Related Function Documentation

template<typename SortPolicy , typename MetricType , typename TreeType >
friend class RASearch< SortPolicy, MetricType, TreeType >
friend

Definition at line 315 of file ra_search_rules.hpp.

Member Data Documentation

template<typename SortPolicy , typename MetricType , typename TreeType >
arma::mat& mlpack::neighbor::RASearchRules< SortPolicy, MetricType, TreeType >::distances
private

The matrix the resultant neighbor distances should be stored in.

Definition at line 213 of file ra_search_rules.hpp.

template<typename SortPolicy , typename MetricType , typename TreeType >
bool mlpack::neighbor::RASearchRules< SortPolicy, MetricType, TreeType >::firstLeafExact
private

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

Definition at line 222 of file ra_search_rules.hpp.

template<typename SortPolicy , typename MetricType , typename TreeType >
MetricType& mlpack::neighbor::RASearchRules< SortPolicy, MetricType, TreeType >::metric
private

The instantiated metric.

Definition at line 216 of file ra_search_rules.hpp.

template<typename SortPolicy , typename MetricType , typename TreeType >
arma::Mat<size_t>& mlpack::neighbor::RASearchRules< SortPolicy, MetricType, TreeType >::neighbors
private

The matrix the resultant neighbor indices should be stored in.

Definition at line 210 of file ra_search_rules.hpp.

template<typename SortPolicy , typename MetricType , typename TreeType >
size_t mlpack::neighbor::RASearchRules< SortPolicy, MetricType, TreeType >::numDistComputations
private
template<typename SortPolicy , typename MetricType , typename TreeType >
arma::Col<size_t> mlpack::neighbor::RASearchRules< SortPolicy, MetricType, TreeType >::numSamplesMade
private

The number of samples made for every query.

Definition at line 231 of file ra_search_rules.hpp.

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

template<typename SortPolicy , typename MetricType , typename TreeType >
size_t mlpack::neighbor::RASearchRules< SortPolicy, MetricType, TreeType >::numSamplesReqd
private

The minimum number of samples required per query.

Definition at line 228 of file ra_search_rules.hpp.

template<typename SortPolicy , typename MetricType , typename TreeType >
const arma::mat& mlpack::neighbor::RASearchRules< SortPolicy, MetricType, TreeType >::querySet
private

The query set.

Definition at line 207 of file ra_search_rules.hpp.

template<typename SortPolicy , typename MetricType , typename TreeType >
const arma::mat& mlpack::neighbor::RASearchRules< SortPolicy, MetricType, TreeType >::referenceSet
private

The reference set.

Definition at line 204 of file ra_search_rules.hpp.

template<typename SortPolicy , typename MetricType , typename TreeType >
bool mlpack::neighbor::RASearchRules< SortPolicy, MetricType, TreeType >::sampleAtLeaves
private

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

Definition at line 219 of file ra_search_rules.hpp.

template<typename SortPolicy , typename MetricType , typename TreeType >
double mlpack::neighbor::RASearchRules< SortPolicy, MetricType, TreeType >::samplingRatio
private

The sampling ratio.

Definition at line 234 of file ra_search_rules.hpp.

template<typename SortPolicy , typename MetricType , typename TreeType >
size_t mlpack::neighbor::RASearchRules< SortPolicy, MetricType, TreeType >::singleSampleLimit
private

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

Definition at line 225 of file ra_search_rules.hpp.

template<typename SortPolicy , typename MetricType , typename TreeType >
TraversalInfoType mlpack::neighbor::RASearchRules< SortPolicy, MetricType, TreeType >::traversalInfo
private

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