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

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

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 neighbor_search_rules.hpp.

Member Typedef Documentation

template<typename SortPolicy , typename MetricType , typename TreeType >

typedef std::pair<double, size_t> mlpack::neighbor::NeighborSearchRules< SortPolicy, MetricType, TreeType >::Candidate

protected

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

Definition at line 166 of file neighbor_search_rules.hpp.

template<typename SortPolicy , typename MetricType , typename TreeType >

typedef std::priority_queue<Candidate, std::vector<Candidate>, CandidateCmp> mlpack::neighbor::NeighborSearchRules< SortPolicy, MetricType, TreeType >::CandidateList

protected

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

Definition at line 178 of file neighbor_search_rules.hpp.

template<typename SortPolicy , typename MetricType , typename TreeType >

typedef tree::TraversalInfo<TreeType> mlpack::neighbor::NeighborSearchRules< SortPolicy, MetricType, TreeType >::TraversalInfoType

Convenience typedef.

Definition at line 151 of file neighbor_search_rules.hpp.

Constructor & Destructor Documentation

template<typename SortPolicy , typename MetricType , typename TreeType >

mlpack::neighbor::NeighborSearchRules< SortPolicy, MetricType, TreeType >::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

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.

Member Function Documentation

template<typename SortPolicy , typename MetricType , typename TreeType >

double mlpack::neighbor::NeighborSearchRules< SortPolicy, MetricType, TreeType >::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

queryIndex	Index of query point.
referenceIndex	Index of reference point.

template<typename SortPolicy , typename MetricType , typename TreeType >

size_t mlpack::neighbor::NeighborSearchRules< SortPolicy, MetricType, TreeType >::BaseCases ( ) const

inline

Get the number of base cases that have been performed.

Definition at line 141 of file neighbor_search_rules.hpp.

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

template<typename SortPolicy , typename MetricType , typename TreeType >

size_t& mlpack::neighbor::NeighborSearchRules< SortPolicy, MetricType, TreeType >::BaseCases ( )

inline

Modify the number of base cases that have been performed.

Definition at line 143 of file neighbor_search_rules.hpp.

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

template<typename SortPolicy , typename MetricType , typename TreeType >

double mlpack::neighbor::NeighborSearchRules< SortPolicy, MetricType, TreeType >::CalculateBound ( TreeType & queryNode ) const

protected

Recalculate the bound for a given query node.

template<typename SortPolicy , typename MetricType , typename TreeType >

size_t mlpack::neighbor::NeighborSearchRules< SortPolicy, MetricType, TreeType >::GetBestChild	(	const size_t	queryIndex,
		TreeType &	referenceNode
	)

Get the child node with the best score.

Parameters

queryIndex	Index of query point.
referenceNode	Candidate node to be recursed into.

template<typename SortPolicy , typename MetricType , typename TreeType >

size_t mlpack::neighbor::NeighborSearchRules< SortPolicy, MetricType, TreeType >::GetBestChild	(	const TreeType &	queryNode,
		TreeType &	referenceNode
	)

Get the child node with the best score.

Parameters

queryNode	Node to be considered.
referenceNode	Candidate node to be recursed into.

template<typename SortPolicy , typename MetricType , typename TreeType >

void mlpack::neighbor::NeighborSearchRules< SortPolicy, MetricType, TreeType >::GetResults	(	arma::Mat< size_t > &	neighbors,
		arma::mat &	distances
	)

Store the list of candidates for each query point in the given matrices.

Parameters

neighbors	Matrix storing lists of neighbors for each query point.
distances	Matrix storing distances of neighbors for each query point.

template<typename SortPolicy , typename MetricType , typename TreeType >

void mlpack::neighbor::NeighborSearchRules< SortPolicy, MetricType, TreeType >::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

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.

template<typename SortPolicy , typename MetricType , typename TreeType >

double mlpack::neighbor::NeighborSearchRules< SortPolicy, MetricType, TreeType >::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

queryIndex	Index of query point.
referenceNode	Candidate node to be recursed into.
oldScore	Old score produced by Score() (or Rescore()).

template<typename SortPolicy , typename MetricType , typename TreeType >

double mlpack::neighbor::NeighborSearchRules< SortPolicy, MetricType, TreeType >::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

queryNode	Candidate query node to recurse into.
referenceNode	Candidate reference node to recurse into.
oldScore	Old score produced by Socre() (or Rescore()).

template<typename SortPolicy , typename MetricType , typename TreeType >

double mlpack::neighbor::NeighborSearchRules< 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).

Parameters

queryIndex	Index of query point.
referenceNode	Candidate node to be recursed into.

template<typename SortPolicy , typename MetricType , typename TreeType >

double mlpack::neighbor::NeighborSearchRules< 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).

Parameters

queryNode	Candidate query node to recurse into.
referenceNode	Candidate reference node to recurse into.

template<typename SortPolicy , typename MetricType , typename TreeType >

size_t mlpack::neighbor::NeighborSearchRules< SortPolicy, MetricType, TreeType >::Scores ( ) const

inline

Get the number of scores that have been performed.

Definition at line 146 of file neighbor_search_rules.hpp.

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

template<typename SortPolicy , typename MetricType , typename TreeType >

size_t& mlpack::neighbor::NeighborSearchRules< SortPolicy, MetricType, TreeType >::Scores ( )

inline

Modify the number of scores that have been performed.

Definition at line 148 of file neighbor_search_rules.hpp.

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

template<typename SortPolicy , typename MetricType , typename TreeType >

const TraversalInfoType& mlpack::neighbor::NeighborSearchRules< SortPolicy, MetricType, TreeType >::TraversalInfo ( ) const

inline

Get the traversal info.

Definition at line 154 of file neighbor_search_rules.hpp.

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

template<typename SortPolicy , typename MetricType , typename TreeType >

TraversalInfoType& mlpack::neighbor::NeighborSearchRules< SortPolicy, MetricType, TreeType >::TraversalInfo ( )

inline

Modify the traversal info.

Definition at line 156 of file neighbor_search_rules.hpp.

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

Member Data Documentation

template<typename SortPolicy , typename MetricType , typename TreeType >

size_t mlpack::neighbor::NeighborSearchRules< SortPolicy, MetricType, TreeType >::baseCases

protected

The number of base cases that have been performed.

Definition at line 203 of file neighbor_search_rules.hpp.

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

template<typename SortPolicy , typename MetricType , typename TreeType >

std::vector<CandidateList> mlpack::neighbor::NeighborSearchRules< SortPolicy, MetricType, TreeType >::candidates

protected

Set of candidate neighbors for each point.

Definition at line 181 of file neighbor_search_rules.hpp.

template<typename SortPolicy , typename MetricType , typename TreeType >

const double mlpack::neighbor::NeighborSearchRules< SortPolicy, MetricType, TreeType >::epsilon

protected

Relative error to be considered in approximate search.

Definition at line 193 of file neighbor_search_rules.hpp.

template<typename SortPolicy , typename MetricType , typename TreeType >

const size_t mlpack::neighbor::NeighborSearchRules< SortPolicy, MetricType, TreeType >::k

protected

Number of neighbors to search for.

Definition at line 184 of file neighbor_search_rules.hpp.

template<typename SortPolicy , typename MetricType , typename TreeType >

double mlpack::neighbor::NeighborSearchRules< SortPolicy, MetricType, TreeType >::lastBaseCase

protected

The last base case result.

Definition at line 200 of file neighbor_search_rules.hpp.

template<typename SortPolicy , typename MetricType , typename TreeType >

size_t mlpack::neighbor::NeighborSearchRules< SortPolicy, MetricType, TreeType >::lastQueryIndex

protected

The last query point BaseCase() was called with.

Definition at line 196 of file neighbor_search_rules.hpp.

template<typename SortPolicy , typename MetricType , typename TreeType >

size_t mlpack::neighbor::NeighborSearchRules< SortPolicy, MetricType, TreeType >::lastReferenceIndex

protected

The last reference point BaseCase() was called with.

Definition at line 198 of file neighbor_search_rules.hpp.

template<typename SortPolicy , typename MetricType , typename TreeType >

MetricType& mlpack::neighbor::NeighborSearchRules< SortPolicy, MetricType, TreeType >::metric

protected

The instantiated metric.

Definition at line 187 of file neighbor_search_rules.hpp.

template<typename SortPolicy , typename MetricType , typename TreeType >

const TreeType::Mat& mlpack::neighbor::NeighborSearchRules< SortPolicy, MetricType, TreeType >::querySet

protected

The query set.

Definition at line 163 of file neighbor_search_rules.hpp.

template<typename SortPolicy , typename MetricType , typename TreeType >

const TreeType::Mat& mlpack::neighbor::NeighborSearchRules< SortPolicy, MetricType, TreeType >::referenceSet

protected

The reference set.

Definition at line 160 of file neighbor_search_rules.hpp.

template<typename SortPolicy , typename MetricType , typename TreeType >

bool mlpack::neighbor::NeighborSearchRules< SortPolicy, MetricType, TreeType >::sameSet

protected

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

Definition at line 190 of file neighbor_search_rules.hpp.

template<typename SortPolicy , typename MetricType , typename TreeType >

size_t mlpack::neighbor::NeighborSearchRules< SortPolicy, MetricType, TreeType >::scores

protected

The number of scores that have been performed.

Definition at line 205 of file neighbor_search_rules.hpp.

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

template<typename SortPolicy , typename MetricType , typename TreeType >

TraversalInfoType mlpack::neighbor::NeighborSearchRules< SortPolicy, MetricType, TreeType >::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 mlpack::neighbor::NeighborSearchRules< SortPolicy, MetricType, TreeType >::TraversalInfo().

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

src/mlpack/methods/neighbor_search/neighbor_search_rules.hpp

Classes

Public Types

Public Member Functions

Protected Types

Protected Member Functions

Protected Attributes

Detailed Description

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

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation

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