The RASearchRules class is a template helper class used by RASearch class when performing rankapproximate search via randomsampling. More...
Public Types  
typedef tree::TraversalInfo< TreeType >  TraversalInfoType 
Public Member Functions  
RASearchRules (const arma::mat &referenceSet, const arma::mat &querySet, const size_t k, 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, const bool sameSet=false)  
Construct the RASearchRules object. More...  
double  BaseCase (const size_t queryIndex, const size_t referenceIndex) 
Get the distance from the query point to the reference point. More...  
void  GetResults (arma::Mat< size_t > &neighbors, arma::mat &distances) 
Store the list of candidates for each query point in the given matrices. More...  
size_t  NumDistComputations () 
size_t  NumEffectiveSamples () 
double  Rescore (const size_t queryIndex, TreeType &referenceNode, const double oldScore) 
Reevaluate the score for recursion order. More...  
double  Rescore (TreeType &queryNode, TreeType &referenceNode, const double oldScore) 
Reevaluate 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 TraversalInfoType &  TraversalInfo () const 
TraversalInfoType &  TraversalInfo () 
The RASearchRules class is a template helper class used by RASearch class when performing rankapproximate search via randomsampling.
SortPolicy  The sort policy for distances. 
MetricType  The metric to use for computation. 
TreeType  The tree type to use; must adhere to the TreeType API. 
Definition at line 33 of file ra_search_rules.hpp.
typedef tree::TraversalInfo<TreeType> TraversalInfoType 
Definition at line 239 of file ra_search_rules.hpp.
RASearchRules  (  const arma::mat &  referenceSet, 
const arma::mat &  querySet,  
const size_t  k,  
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 , 

const bool  sameSet = false 

) 
Construct the RASearchRules object.
This is usually done from within the RASearch class at search time.
referenceSet  Set of reference data. 
querySet  Set of query data. 
k  Number of neighbors to search for. 
metric  Instantiated metric. 
tau  The rankapproximation in percentile of the data. 
alpha  The desired success probability. 
naive  If true, the rankapproximate search will be performed by directly sampling the whole set instead of using the stratified sampling on the tree. 
sampleAtLeaves  Sample at leaves for faster but less accurate computation. 
firstLeafExact  Traverse to the first leaf without approximation. 
singleSampleLimit  The limit on the largest node that can be approximated by sampling. 
sameSet  If true, the query and reference set are taken to be the same, and a query point will not return itself in the results. 
double BaseCase  (  const size_t  queryIndex, 
const size_t  referenceIndex  
) 
Get the distance from the query point to the reference point.
This will update the list of candidates with the new point if appropriate.
queryIndex  Index of query point. 
referenceIndex  Index of reference point. 
void GetResults  (  arma::Mat< size_t > &  neighbors, 
arma::mat &  distances  
) 
Store the list of candidates for each query point in the given matrices.
neighbors  Matrix storing lists of neighbors for each query point. 
distances  Matrix storing distances of neighbors for each query point. 

inline 
Definition at line 230 of file ra_search_rules.hpp.

inline 
Definition at line 231 of file ra_search_rules.hpp.
double Rescore  (  const size_t  queryIndex, 
TreeType &  referenceNode,  
const double  oldScore  
) 
Reevaluate 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 rankapproximation, 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'.
double Rescore  (  TreeType &  queryNode, 
TreeType &  referenceNode,  
const double  oldScore  
) 
Reevaluate 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 rankapproximation, 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 querytree 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.
queryNode  Candidate query node to recurse into. 
referenceNode  Candidate reference node to recurse into. 
oldScore  Old score produced by Socre() (or Rescore()). 
double 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 rankapproximation, 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 treetraversal.
queryIndex  Index of query point. 
referenceNode  Candidate node to be recursed into. 
Referenced by RASearchRules< SortPolicy, MetricType, TreeType >::TraversalInfo().
double 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 rankapproximation, 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 treetraversal.
queryIndex  Index of query point. 
referenceNode  Candidate node to be recursed into. 
baseCaseResult  Result of BaseCase(queryIndex, referenceNode). 
double 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 rankapproximation, 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 querytree 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.
queryNode  Candidate query node to recurse into. 
referenceNode  Candidate reference node to recurse into. 
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).
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 rankapproximation, 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 querytree 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.
queryNode  Candidate query node to recurse into. 
referenceNode  Candidate reference node to recurse into. 
baseCaseResult  Result of BaseCase(queryIndex, referenceNode). 

inline 
Definition at line 241 of file ra_search_rules.hpp.

inline 
Definition at line 242 of file ra_search_rules.hpp.
References RASearchRules< SortPolicy, MetricType, TreeType >::Score().