mlpack  2.2.5
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
Classes | Public Types | Public Member Functions | Protected Types | Protected Member Functions | Protected Attributes | List of all members
NeighborSearchRules< SortPolicy, MetricType, TreeType > Class Template Reference

The NeighborSearchRules class is a template helper class used by NeighborSearch class when performing distance-based 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...
 
double Rescore (const size_t queryIndex, TreeType &referenceNode, const double oldScore) const
 Re-evaluate the score for recursion order. More...
 
double Rescore (TreeType &queryNode, TreeType &referenceNode, const double oldScore) const
 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 (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 TraversalInfoTypeTraversalInfo () const
 Get the traversal info. More...
 
TraversalInfoTypeTraversalInfo ()
 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< CandidateListcandidates
 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...
 

Detailed Description

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

The NeighborSearchRules class is a template helper class used by NeighborSearch class when performing distance-based 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.

Template Parameters
SortPolicyThe sort policy for distances.
MetricTypeThe metric to use for computation.
TreeTypeThe tree type to use; must adhere to the TreeType API.

Definition at line 33 of file neighbor_search_rules.hpp.

Member Typedef Documentation

typedef std::pair<double, size_t> Candidate
protected

Candidate represents a possible candidate neighbor (distance, index).

Definition at line 166 of file neighbor_search_rules.hpp.

typedef std::priority_queue<Candidate, std::vector<Candidate>, CandidateCmp> CandidateList
protected

Use a priority queue to represent the list of candidate neighbors.

Definition at line 178 of file neighbor_search_rules.hpp.

Convenience typedef.

Definition at line 151 of file neighbor_search_rules.hpp.

Constructor & Destructor Documentation

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.

Parameters
referenceSetSet of reference data.
querySetSet of query data.
kNumber of neighbors to search for.
metricInstantiated metric.
epsilonRelative approximate error.
sameSetIf true, the query and reference set are taken to be the same, and a query point will not return itself in the results.

Member Function Documentation

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).

Parameters
queryIndexIndex of query point.
referenceIndexIndex of reference point.
size_t BaseCases ( ) const
inline

Get the number of base cases that have been performed.

Definition at line 141 of file neighbor_search_rules.hpp.

References NeighborSearchRules< SortPolicy, MetricType, TreeType >::baseCases.

size_t& BaseCases ( )
inline

Modify 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.

double CalculateBound ( TreeType &  queryNode) const
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.

Parameters
queryIndexIndex of query point.
referenceNodeCandidate node to be recursed into.
size_t GetBestChild ( const TreeType &  queryNode,
TreeType &  referenceNode 
)

Get the child node with the best score.

Parameters
queryNodeNode to be considered.
referenceNodeCandidate 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.

Parameters
neighborsMatrix storing lists of neighbors for each query point.
distancesMatrix storing distances of neighbors for each query point.
void InsertNeighbor ( const size_t  queryIndex,
const size_t  neighbor,
const double  distance 
)
protected

Helper function to insert a point into the list of candidate points.

Parameters
queryIndexIndex of point whose neighbors we are inserting into.
neighborIndex of reference point which is being inserted.
distanceDistance from query point to reference point.
double Rescore ( const size_t  queryIndex,
TreeType &  referenceNode,
const double  oldScore 
) const

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.

Parameters
queryIndexIndex of query point.
referenceNodeCandidate node to be recursed into.
oldScoreOld score produced by Score() (or Rescore()).
double Rescore ( TreeType &  queryNode,
TreeType &  referenceNode,
const double  oldScore 
) const

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.

Parameters
queryNodeCandidate query node to recurse into.
referenceNodeCandidate reference node to recurse into.
oldScoreOld 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).

Parameters
queryIndexIndex of query point.
referenceNodeCandidate 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).

Parameters
queryNodeCandidate query node to recurse into.
referenceNodeCandidate reference node to recurse into.
size_t Scores ( ) const
inline

Get the number of scores that have been performed.

Definition at line 146 of file neighbor_search_rules.hpp.

References NeighborSearchRules< SortPolicy, MetricType, TreeType >::scores.

size_t& Scores ( )
inline

Modify the number of scores that have been performed.

Definition at line 148 of file neighbor_search_rules.hpp.

References NeighborSearchRules< SortPolicy, MetricType, TreeType >::scores.

const TraversalInfoType& TraversalInfo ( ) const
inline

Get the traversal info.

Definition at line 154 of file neighbor_search_rules.hpp.

References NeighborSearchRules< SortPolicy, MetricType, TreeType >::traversalInfo.

TraversalInfoType& TraversalInfo ( )
inline

Modify the traversal info.

Definition at line 156 of file neighbor_search_rules.hpp.

References NeighborSearchRules< SortPolicy, MetricType, TreeType >::traversalInfo.

Member Data Documentation

size_t baseCases
protected

The number of base cases that have been performed.

Definition at line 203 of file neighbor_search_rules.hpp.

Referenced by NeighborSearchRules< SortPolicy, MetricType, TreeType >::BaseCases().

std::vector<CandidateList> candidates
protected

Set of candidate neighbors for each point.

Definition at line 181 of file neighbor_search_rules.hpp.

const double epsilon
protected

Relative error to be considered in approximate search.

Definition at line 193 of file neighbor_search_rules.hpp.

const size_t k
protected

Number of neighbors to search for.

Definition at line 184 of file neighbor_search_rules.hpp.

double lastBaseCase
protected

The last base case result.

Definition at line 200 of file neighbor_search_rules.hpp.

size_t lastQueryIndex
protected

The last query point BaseCase() was called with.

Definition at line 196 of file neighbor_search_rules.hpp.

size_t lastReferenceIndex
protected

The last reference point BaseCase() was called with.

Definition at line 198 of file neighbor_search_rules.hpp.

MetricType& metric
protected

The instantiated metric.

Definition at line 187 of file neighbor_search_rules.hpp.

const TreeType::Mat& querySet
protected

The query set.

Definition at line 163 of file neighbor_search_rules.hpp.

const TreeType::Mat& referenceSet
protected

The reference set.

Definition at line 160 of file neighbor_search_rules.hpp.

bool sameSet
protected

Denotes whether or not the reference and query sets are the same.

Definition at line 190 of file neighbor_search_rules.hpp.

size_t scores
protected

The number of scores that have been performed.

Definition at line 205 of file neighbor_search_rules.hpp.

Referenced by NeighborSearchRules< SortPolicy, MetricType, TreeType >::Scores().

TraversalInfoType traversalInfo
protected

Traversal info for the parent combination; this is updated by the traversal before each call to Score().

Definition at line 209 of file neighbor_search_rules.hpp.

Referenced by NeighborSearchRules< SortPolicy, MetricType, TreeType >::TraversalInfo().


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