The NeighborSearchRules class is a template helper class used by NeighborSearch class when performing distancebased neighbor searches. More...
Classes  
struct  CandidateCmp 
Compare two candidates based on the distance. More...  
Public Types  
typedef tree::TraversalInfo< TreeType >  TraversalInfoType 
Convenience typedef. More...  
Public Member Functions  
NeighborSearchRules (const typename TreeType::Mat &referenceSet, const typename TreeType::Mat &querySet, const size_t k, MetricType &metric, const double epsilon=0, const bool sameSet=false)  
Construct the NeighborSearchRules object. More...  
double  BaseCase (const size_t queryIndex, const size_t referenceIndex) 
Get the distance from the query point to the reference point. More...  
size_t  BaseCases () const 
Get the number of base cases that have been performed. More...  
size_t &  BaseCases () 
Modify the number of base cases that have been performed. More...  
size_t  GetBestChild (const size_t queryIndex, TreeType &referenceNode) 
Get the child node with the best score. More...  
size_t  GetBestChild (const TreeType &queryNode, TreeType &referenceNode) 
Get the child node with the best score. 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  MinimumBaseCases () const 
Get the minimum number of base cases we need to perform to have acceptable results. More...  
double  Rescore (const size_t queryIndex, TreeType &referenceNode, const double oldScore) const 
Reevaluate the score for recursion order. More...  
double  Rescore (TreeType &queryNode, TreeType &referenceNode, const double oldScore) const 
Reevaluate the score for recursion order. More...  
double  Score (const size_t queryIndex, TreeType &referenceNode) 
Get the score for recursion order. More...  
double  Score (TreeType &queryNode, TreeType &referenceNode) 
Get the score for recursion order. More...  
size_t  Scores () const 
Get the number of scores that have been performed. More...  
size_t &  Scores () 
Modify the number of scores that have been performed. More...  
const TraversalInfoType &  TraversalInfo () const 
Get the traversal info. More...  
TraversalInfoType &  TraversalInfo () 
Modify the traversal info. More...  
Protected Types  
typedef std::pair< double, size_t >  Candidate 
Candidate represents a possible candidate neighbor (distance, index). More...  
typedef std::priority_queue< Candidate, std::vector< Candidate >, CandidateCmp >  CandidateList 
Use a priority queue to represent the list of candidate neighbors. More...  
Protected Member Functions  
double  CalculateBound (TreeType &queryNode) const 
Recalculate the bound for a given query node. More...  
void  InsertNeighbor (const size_t queryIndex, const size_t neighbor, const double distance) 
Helper function to insert a point into the list of candidate points. More...  
Protected Attributes  
size_t  baseCases 
The number of base cases that have been performed. More...  
std::vector< CandidateList >  candidates 
Set of candidate neighbors for each point. More...  
const double  epsilon 
Relative error to be considered in approximate search. More...  
const size_t  k 
Number of neighbors to search for. More...  
double  lastBaseCase 
The last base case result. More...  
size_t  lastQueryIndex 
The last query point BaseCase() was called with. More...  
size_t  lastReferenceIndex 
The last reference point BaseCase() was called with. More...  
MetricType &  metric 
The instantiated metric. More...  
const TreeType::Mat &  querySet 
The query set. More...  
const TreeType::Mat &  referenceSet 
The reference set. More...  
bool  sameSet 
Denotes whether or not the reference and query sets are the same. More...  
size_t  scores 
The number of scores that have been performed. More...  
TraversalInfoType  traversalInfo 
Traversal info for the parent combination; this is updated by the traversal before each call to Score(). More...  
The NeighborSearchRules class is a template helper class used by NeighborSearch class when performing distancebased neighbor searches.
For each point in the query dataset, it keeps track of the k neighbors in the reference dataset which have the 'best' distance according to a given sorting policy.
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 35 of file neighbor_search_rules.hpp.

protected 
Candidate represents a possible candidate neighbor (distance, index).
Definition at line 172 of file neighbor_search_rules.hpp.

protected 
Use a priority queue to represent the list of candidate neighbors.
Definition at line 184 of file neighbor_search_rules.hpp.
typedef tree::TraversalInfo<TreeType> TraversalInfoType 
Convenience typedef.
Definition at line 153 of file neighbor_search_rules.hpp.
NeighborSearchRules  (  const typename TreeType::Mat &  referenceSet, 
const typename TreeType::Mat &  querySet,  
const size_t  k,  
MetricType &  metric,  
const double  epsilon = 0 , 

const bool  sameSet = false 

) 
Construct the NeighborSearchRules object.
This is usually done from within the NeighborSearch class at search time.
referenceSet  Set of reference data. 
querySet  Set of query data. 
k  Number of neighbors to search for. 
metric  Instantiated metric. 
epsilon  Relative approximate error. 
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 and will track the number of base cases (number of points evaluated).
queryIndex  Index of query point. 
referenceIndex  Index of reference point. 

inline 
Get the number of base cases that have been performed.
Definition at line 143 of file neighbor_search_rules.hpp.
References NeighborSearchRules< SortPolicy, MetricType, TreeType >::baseCases.

inline 
Modify the number of base cases that have been performed.
Definition at line 145 of file neighbor_search_rules.hpp.
References NeighborSearchRules< SortPolicy, MetricType, TreeType >::baseCases.

protected 
Recalculate the bound for a given query node.
size_t GetBestChild  (  const size_t  queryIndex, 
TreeType &  referenceNode  
) 
Get the child node with the best score.
queryIndex  Index of query point. 
referenceNode  Candidate node to be recursed into. 
size_t GetBestChild  (  const TreeType &  queryNode, 
TreeType &  referenceNode  
) 
Get the child node with the best score.
queryNode  Node to be considered. 
referenceNode  Candidate node to be recursed into. 
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. 

protected 
Helper function to insert a point into the list of candidate points.
queryIndex  Index of point whose neighbors we are inserting into. 
neighbor  Index of reference point which is being inserted. 
distance  Distance from query point to reference point. 

inline 
Get the minimum number of base cases we need to perform to have acceptable results.
This is only needed in defeatist search mode.
Definition at line 162 of file neighbor_search_rules.hpp.
References NeighborSearchRules< SortPolicy, MetricType, TreeType >::k.
double Rescore  (  const size_t  queryIndex, 
TreeType &  referenceNode,  
const double  oldScore  
)  const 
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.
double Rescore  (  TreeType &  queryNode, 
TreeType &  referenceNode,  
const double  oldScore  
)  const 
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.
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).
queryIndex  Index of query point. 
referenceNode  Candidate node to be recursed into. 
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).
queryNode  Candidate query node to recurse into. 
referenceNode  Candidate reference node to recurse into. 

inline 
Get the number of scores that have been performed.
Definition at line 148 of file neighbor_search_rules.hpp.
References NeighborSearchRules< SortPolicy, MetricType, TreeType >::scores.

inline 
Modify the number of scores that have been performed.
Definition at line 150 of file neighbor_search_rules.hpp.
References NeighborSearchRules< SortPolicy, MetricType, TreeType >::scores.

inline 
Get the traversal info.
Definition at line 156 of file neighbor_search_rules.hpp.
References NeighborSearchRules< SortPolicy, MetricType, TreeType >::traversalInfo.

inline 
Modify the traversal info.
Definition at line 158 of file neighbor_search_rules.hpp.
References NeighborSearchRules< SortPolicy, MetricType, TreeType >::traversalInfo.

protected 
The number of base cases that have been performed.
Definition at line 209 of file neighbor_search_rules.hpp.
Referenced by NeighborSearchRules< SortPolicy, MetricType, TreeType >::BaseCases().

protected 
Set of candidate neighbors for each point.
Definition at line 187 of file neighbor_search_rules.hpp.

protected 
Relative error to be considered in approximate search.
Definition at line 199 of file neighbor_search_rules.hpp.

protected 
Number of neighbors to search for.
Definition at line 190 of file neighbor_search_rules.hpp.
Referenced by NeighborSearchRules< SortPolicy, MetricType, TreeType >::MinimumBaseCases().

protected 
The last base case result.
Definition at line 206 of file neighbor_search_rules.hpp.

protected 
The last query point BaseCase() was called with.
Definition at line 202 of file neighbor_search_rules.hpp.

protected 
The last reference point BaseCase() was called with.
Definition at line 204 of file neighbor_search_rules.hpp.

protected 
The instantiated metric.
Definition at line 193 of file neighbor_search_rules.hpp.

protected 
The query set.
Definition at line 169 of file neighbor_search_rules.hpp.

protected 
The reference set.
Definition at line 166 of file neighbor_search_rules.hpp.

protected 
Denotes whether or not the reference and query sets are the same.
Definition at line 196 of file neighbor_search_rules.hpp.

protected 
The number of scores that have been performed.
Definition at line 211 of file neighbor_search_rules.hpp.
Referenced by NeighborSearchRules< SortPolicy, MetricType, TreeType >::Scores().

protected 
Traversal info for the parent combination; this is updated by the traversal before each call to Score().
Definition at line 215 of file neighbor_search_rules.hpp.
Referenced by NeighborSearchRules< SortPolicy, MetricType, TreeType >::TraversalInfo().