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 >, CandidateCmpCandidateList
 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 35 of file neighbor_search_rules.hpp.

Member Typedef Documentation

◆ Candidate

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

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

Definition at line 168 of file neighbor_search_rules.hpp.

◆ CandidateList

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 180 of file neighbor_search_rules.hpp.

◆ TraversalInfoType

Convenience typedef.

Definition at line 153 of file neighbor_search_rules.hpp.

Constructor & Destructor Documentation

◆ NeighborSearchRules()

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

◆ BaseCase()

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.

◆ BaseCases() [1/2]

size_t BaseCases ( ) const
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.

◆ BaseCases() [2/2]

size_t& 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.

◆ CalculateBound()

double CalculateBound ( TreeType &  queryNode) const
protected

Recalculate the bound for a given query node.

◆ GetBestChild() [1/2]

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.

◆ GetBestChild() [2/2]

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.

◆ GetResults()

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.

◆ InsertNeighbor()

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.

◆ Rescore() [1/2]

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

◆ Rescore() [2/2]

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

◆ Score() [1/2]

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.

◆ Score() [2/2]

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.

◆ Scores() [1/2]

size_t Scores ( ) const
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.

◆ Scores() [2/2]

size_t& 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.

◆ TraversalInfo() [1/2]

const TraversalInfoType& TraversalInfo ( ) const
inline

Get the traversal info.

Definition at line 156 of file neighbor_search_rules.hpp.

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

◆ TraversalInfo() [2/2]

TraversalInfoType& TraversalInfo ( )
inline

Modify the traversal info.

Definition at line 158 of file neighbor_search_rules.hpp.

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

Member Data Documentation

◆ baseCases

size_t baseCases
protected

The number of base cases that have been performed.

Definition at line 205 of file neighbor_search_rules.hpp.

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

◆ candidates

std::vector<CandidateList> candidates
protected

Set of candidate neighbors for each point.

Definition at line 183 of file neighbor_search_rules.hpp.

◆ epsilon

const double epsilon
protected

Relative error to be considered in approximate search.

Definition at line 195 of file neighbor_search_rules.hpp.

◆ k

const size_t k
protected

Number of neighbors to search for.

Definition at line 186 of file neighbor_search_rules.hpp.

◆ lastBaseCase

double lastBaseCase
protected

The last base case result.

Definition at line 202 of file neighbor_search_rules.hpp.

◆ lastQueryIndex

size_t lastQueryIndex
protected

The last query point BaseCase() was called with.

Definition at line 198 of file neighbor_search_rules.hpp.

◆ lastReferenceIndex

size_t lastReferenceIndex
protected

The last reference point BaseCase() was called with.

Definition at line 200 of file neighbor_search_rules.hpp.

◆ metric

MetricType& metric
protected

The instantiated metric.

Definition at line 189 of file neighbor_search_rules.hpp.

◆ querySet

const TreeType::Mat& querySet
protected

The query set.

Definition at line 165 of file neighbor_search_rules.hpp.

◆ referenceSet

const TreeType::Mat& referenceSet
protected

The reference set.

Definition at line 162 of file neighbor_search_rules.hpp.

◆ sameSet

bool sameSet
protected

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

Definition at line 192 of file neighbor_search_rules.hpp.

◆ scores

size_t scores
protected

The number of scores that have been performed.

Definition at line 207 of file neighbor_search_rules.hpp.

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

◆ traversalInfo

TraversalInfoType traversalInfo
protected

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

Definition at line 211 of file neighbor_search_rules.hpp.

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


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