The RASearchRules class is a template helper class used by RASearch class when performing rank-approximate search via random-sampling. More...

Classes
struct	CandidateCmp
	Compare two candidates based on the distance. 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)
	Re-evaluate the score for recursion order. More...

double	Rescore (TreeType &queryNode, TreeType &referenceNode, const double oldScore)
	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 (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 ()

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

Private Member Functions
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...

double	Score (const size_t queryIndex, TreeType &referenceNode, const double distance, const double bestDistance)
	Perform actual scoring for single-tree case. More...

double	Score (TreeType &queryNode, TreeType &referenceNode, const double distance, const double bestDistance)
	Perform actual scoring for dual-tree case. More...

Private Attributes
std::vector< CandidateList >	candidates
	Set of candidate neighbors for each point. More...

bool	firstLeafExact
	Whether to do exact computation on the first leaf before any sampling. More...

const size_t	k
	Number of neighbors to search for. More...

MetricType &	metric
	The instantiated metric. More...

size_t	numDistComputations

arma::Col< size_t >	numSamplesMade
	The number of samples made for every query. More...

size_t	numSamplesReqd
	The minimum number of samples required per query. More...

const arma::mat &	querySet
	The query set. More...

const arma::mat &	referenceSet
	The reference set. More...

bool	sameSet
	If the query and reference set are identical, this is true. More...

bool	sampleAtLeaves
	Whether to sample at leaves or just use all of it. More...

double	samplingRatio
	The sampling ratio. More...

size_t	singleSampleLimit
	The limit on the largest node that can be approximated by sampling. More...

TraversalInfoType	traversalInfo

Detailed Description

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

The RASearchRules class is a template helper class used by RASearch class when performing rank-approximate search via random-sampling.

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 31 of file ra_search_rules.hpp.

Member Typedef Documentation

template<typename SortPolicy , typename MetricType , typename TreeType >

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

private

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

Definition at line 250 of file ra_search_rules.hpp.

template<typename SortPolicy , typename MetricType , typename TreeType >

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

private

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

Definition at line 262 of file ra_search_rules.hpp.

template<typename SortPolicy , typename MetricType , typename TreeType >

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

Definition at line 237 of file ra_search_rules.hpp.

Constructor & Destructor Documentation

template<typename SortPolicy , typename MetricType , typename TreeType >

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

Parameters

referenceSet	Set of reference data.
querySet	Set of query data.
k	Number of neighbors to search for.
metric	Instantiated metric.
tau	The rank-approximation in percentile of the data.
alpha	The desired success probability.
naive	If true, the rank-approximate 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.

Member Function Documentation

template<typename SortPolicy , typename MetricType , typename TreeType >

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

Parameters

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

template<typename SortPolicy , typename MetricType , typename TreeType >

void mlpack::neighbor::RASearchRules< 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::RASearchRules< SortPolicy, MetricType, TreeType >::InsertNeighbor	(	const size_t	queryIndex,
		const size_t	neighbor,
		const double	distance
	)

private

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 >

size_t mlpack::neighbor::RASearchRules< SortPolicy, MetricType, TreeType >::NumDistComputations ( )

inline

Definition at line 228 of file ra_search_rules.hpp.

References mlpack::neighbor::RASearchRules< SortPolicy, MetricType, TreeType >::numDistComputations.

template<typename SortPolicy , typename MetricType , typename TreeType >

size_t mlpack::neighbor::RASearchRules< SortPolicy, MetricType, TreeType >::NumEffectiveSamples ( )

inline

Definition at line 229 of file ra_search_rules.hpp.

References mlpack::neighbor::RASearchRules< SortPolicy, MetricType, TreeType >::numSamplesMade.

template<typename SortPolicy , typename MetricType , typename TreeType >

double mlpack::neighbor::RASearchRules< SortPolicy, MetricType, TreeType >::Rescore	(	const size_t	queryIndex,
		TreeType &	referenceNode,
		const double	oldScore
	)

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.

For rank-approximation, 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'.

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::RASearchRules< SortPolicy, MetricType, TreeType >::Rescore	(	TreeType &	queryNode,
		TreeType &	referenceNode,
		const double	oldScore
	)

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.

For the rank-approximation, 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 query-tree 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.

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

For rank-approximation, 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 tree-traversal.

Parameters

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

template<typename SortPolicy , typename MetricType , typename TreeType >

double mlpack::neighbor::RASearchRules< SortPolicy, MetricType, TreeType >::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 rank-approximation, 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 tree-traversal.

Parameters

queryIndex	Index of query point.
referenceNode	Candidate node to be recursed into.
baseCaseResult	Result of BaseCase(queryIndex, referenceNode).

template<typename SortPolicy , typename MetricType , typename TreeType >

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

For the rank-approximation, 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 query-tree 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.

Parameters

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

template<typename SortPolicy , typename MetricType , typename TreeType >

double mlpack::neighbor::RASearchRules< SortPolicy, MetricType, TreeType >::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 rank-approximation, 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 query-tree 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.

Parameters

queryNode	Candidate query node to recurse into.
referenceNode	Candidate reference node to recurse into.
baseCaseResult	Result of BaseCase(queryIndex, referenceNode).

template<typename SortPolicy , typename MetricType , typename TreeType >

double mlpack::neighbor::RASearchRules< SortPolicy, MetricType, TreeType >::Score	(	const size_t	queryIndex,
		TreeType &	referenceNode,
		const double	distance,
		const double	bestDistance
	)

private

Perform actual scoring for single-tree case.

template<typename SortPolicy , typename MetricType , typename TreeType >

double mlpack::neighbor::RASearchRules< SortPolicy, MetricType, TreeType >::Score	(	TreeType &	queryNode,
		TreeType &	referenceNode,
		const double	distance,
		const double	bestDistance
	)

private

Perform actual scoring for dual-tree case.

template<typename SortPolicy , typename MetricType , typename TreeType >

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

inline

Definition at line 239 of file ra_search_rules.hpp.

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

template<typename SortPolicy , typename MetricType , typename TreeType >

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

inline

Definition at line 240 of file ra_search_rules.hpp.

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

Member Data Documentation

template<typename SortPolicy , typename MetricType , typename TreeType >

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

private

Set of candidate neighbors for each point.

Definition at line 265 of file ra_search_rules.hpp.

template<typename SortPolicy , typename MetricType , typename TreeType >

bool mlpack::neighbor::RASearchRules< SortPolicy, MetricType, TreeType >::firstLeafExact

private

Whether to do exact computation on the first leaf before any sampling.

Definition at line 277 of file ra_search_rules.hpp.

template<typename SortPolicy , typename MetricType , typename TreeType >

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

private

Number of neighbors to search for.

Definition at line 268 of file ra_search_rules.hpp.

template<typename SortPolicy , typename MetricType , typename TreeType >

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

private

The instantiated metric.

Definition at line 271 of file ra_search_rules.hpp.

template<typename SortPolicy , typename MetricType , typename TreeType >

size_t mlpack::neighbor::RASearchRules< SortPolicy, MetricType, TreeType >::numDistComputations

private

Definition at line 292 of file ra_search_rules.hpp.

Referenced by mlpack::neighbor::RASearchRules< SortPolicy, MetricType, TreeType >::NumDistComputations().

template<typename SortPolicy , typename MetricType , typename TreeType >

arma::Col<size_t> mlpack::neighbor::RASearchRules< SortPolicy, MetricType, TreeType >::numSamplesMade

private

The number of samples made for every query.

Definition at line 286 of file ra_search_rules.hpp.

Referenced by mlpack::neighbor::RASearchRules< SortPolicy, MetricType, TreeType >::NumEffectiveSamples().

template<typename SortPolicy , typename MetricType , typename TreeType >

size_t mlpack::neighbor::RASearchRules< SortPolicy, MetricType, TreeType >::numSamplesReqd

private

The minimum number of samples required per query.

Definition at line 283 of file ra_search_rules.hpp.

template<typename SortPolicy , typename MetricType , typename TreeType >

const arma::mat& mlpack::neighbor::RASearchRules< SortPolicy, MetricType, TreeType >::querySet

private

The query set.

Definition at line 247 of file ra_search_rules.hpp.

template<typename SortPolicy , typename MetricType , typename TreeType >

const arma::mat& mlpack::neighbor::RASearchRules< SortPolicy, MetricType, TreeType >::referenceSet

private

The reference set.

Definition at line 244 of file ra_search_rules.hpp.

template<typename SortPolicy , typename MetricType , typename TreeType >

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

private

If the query and reference set are identical, this is true.

Definition at line 295 of file ra_search_rules.hpp.

template<typename SortPolicy , typename MetricType , typename TreeType >

bool mlpack::neighbor::RASearchRules< SortPolicy, MetricType, TreeType >::sampleAtLeaves

private

Whether to sample at leaves or just use all of it.

Definition at line 274 of file ra_search_rules.hpp.

template<typename SortPolicy , typename MetricType , typename TreeType >

double mlpack::neighbor::RASearchRules< SortPolicy, MetricType, TreeType >::samplingRatio

private

The sampling ratio.

Definition at line 289 of file ra_search_rules.hpp.

template<typename SortPolicy , typename MetricType , typename TreeType >

size_t mlpack::neighbor::RASearchRules< SortPolicy, MetricType, TreeType >::singleSampleLimit

private

The limit on the largest node that can be approximated by sampling.

Definition at line 280 of file ra_search_rules.hpp.

template<typename SortPolicy , typename MetricType , typename TreeType >

TraversalInfoType mlpack::neighbor::RASearchRules< SortPolicy, MetricType, TreeType >::traversalInfo

private

Definition at line 297 of file ra_search_rules.hpp.

Referenced by mlpack::neighbor::RASearchRules< SortPolicy, MetricType, TreeType >::TraversalInfo().

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

src/mlpack/methods/rann/ra_search_rules.hpp

Classes

Public Types

Public Member Functions

Private Types

Private Member Functions

Private Attributes

Detailed Description

template<typename SortPolicy, typename MetricType, typename TreeType> class mlpack::neighbor::RASearchRules< 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::RASearchRules< SortPolicy, MetricType, TreeType >