knncolle::VptreeSearcher< Index_, Data_, Distance_, DistanceMetric_ > Class Template Reference

VP-tree searcher. More...

#include <Vptree.hpp>

Inheritance diagram for knncolle::VptreeSearcher< Index_, Data_, Distance_, DistanceMetric_ >:

Collaboration diagram for knncolle::VptreeSearcher< Index_, Data_, Distance_, DistanceMetric_ >:

Public Member Functions
void	search (Index_ i, Index_ k, std::vector< Index_ > *output_indices, std::vector< Distance_ > *output_distances)
void	search (const Data_ *query, Index_ k, std::vector< Index_ > *output_indices, std::vector< Distance_ > *output_distances)
bool	can_search_all () const
Index_	search_all (Index_ i, Distance_ d, std::vector< Index_ > *output_indices, std::vector< Distance_ > *output_distances)
Index_	search_all (const Data_ *query, Distance_ d, std::vector< Index_ > *output_indices, std::vector< Distance_ > *output_distances)
Public Member Functions inherited from knncolle::Searcher< Index_, Data_, Distance_ >

Detailed Description

template<typename Index_, typename Data_, typename Distance_, class DistanceMetric_>
class knncolle::VptreeSearcher< Index_, Data_, Distance_, DistanceMetric_ >

VP-tree searcher.

Instances of this class are usually constructed using VptreePrebuilt::initialize().

Template Parameters

Index_	Integer type for the indices.
Data_	Numeric type for the input and query data.
Distance_	Floating point type for the distances.
DistanceMetric_	Class implementing the distance metric calculation. This should satisfy the DistanceMetric interface.

Member Function Documentation

can_search_all()

template<typename Index_ , typename Data_ , typename Distance_ , class DistanceMetric_ >

bool knncolle::VptreeSearcher< Index_, Data_, Distance_, DistanceMetric_ >::can_search_all ( ) const

inlinevirtual

It is expected that the return value of this method should be constant throughout the lifetime of any Searcher instance.

Returns

Whether this instance has an implementation of the search_all() method.

Reimplemented from knncolle::Searcher< Index_, Data_, Distance_ >.

search() [1/2]

template<typename Index_ , typename Data_ , typename Distance_ , class DistanceMetric_ >

void knncolle::VptreeSearcher< Index_, Data_, Distance_, DistanceMetric_ >::search ( const Data_ * query, Index_ k, std::vector< Index_ > * output_indices, std::vector< Distance_ > * output_distances )

inlinevirtual

Find the nearest neighbors of a new observation.

Parameters

	query	Pointer to an array of length equal to Prebuilt::num_dimensions(), containing the coordinates of the query point.
	k	The number of neighbors to identify. This should be a non-negative integer that is no greater than the number of observations in Prebuilt::num_observations().
[out]	output_indices	Pointer to a vector, to be filled with the identities of the nearest neighbors in order of increasing distance. On output, the length of the vector should be equal to k. All entries should be unique and less than Prebuilt::num_observations(). Optionally NULL, in which case no indices are returned.
[out]	output_distances	Pointer to a vector, to be filled with the distances of the nearest neighbors. This corresponds to the indices reported in output_indices. Optionally NULL, in which case no distances are returned.

Implements knncolle::Searcher< Index_, Data_, Distance_ >.

search() [2/2]

template<typename Index_ , typename Data_ , typename Distance_ , class DistanceMetric_ >

void knncolle::VptreeSearcher< Index_, Data_, Distance_, DistanceMetric_ >::search ( Index_ i, Index_ k, std::vector< Index_ > * output_indices, std::vector< Distance_ > * output_distances )

inlinevirtual

Find the nearest neighbors of the i-th observation in the dataset.

Parameters

	i	The index of the observation of interest. This should be non-negative and less than the total number of observations in Prebuilt::num_observations().
	k	The number of neighbors to identify. This should be a non-negative integer that is less than the total number of observations in Prebuilt::num_observations(). (Except if Prebuilt::num_observations() == 0, in which case the only valid choice for k is also zero.) Users can call cap_k() to easily cap k based on Prebuilt::num_observations().
[out]	output_indices	Pointer to a vector, to be filled with the identities of the nearest neighbors in order of increasing distance. On output, the length of the vector should be equal to k. All entries should be unique and less than Prebuilt::num_observations(). This vector is guaranteed to not contain i itself. Optionally NULL, in which case no indices are returned.
[out]	output_distances	Pointer to a vector, to be filled with the distances of the nearest neighbors. This corresponds to the indices reported in output_indices. Optionally NULL, in which case no distances are returned.

Implements knncolle::Searcher< Index_, Data_, Distance_ >.

search_all() [1/2]

template<typename Index_ , typename Data_ , typename Distance_ , class DistanceMetric_ >

Index_ knncolle::VptreeSearcher< Index_, Data_, Distance_, DistanceMetric_ >::search_all ( const Data_ * query, Distance_ distance, std::vector< Index_ > * output_indices, std::vector< Distance_ > * output_distances )

inlinevirtual

Find all neighbors of a new observation within a certain distance. This method is optional and may not be implemented by subclasses, so applications should check can_search_all() before attempting a call. A run-time exception is thrown if this method is called on a subclass that does not implement it.

Parameters

	query	Pointer to an array of length equal to Prebuilt::num_dimensions(), containing the coordinates of the query point.
	distance	The distance in which to consider neighbors.
[out]	output_indices	Pointer to a vector, to be filled with the identities of the nearest neighbors in order of increasing distance. Optionally NULL, in which case no indices are returned.
[out]	output_distances	Pointer to a vector, to be filled with the distances of the nearest neighbors. This corresponds to the indices reported in output_indices. Optionally NULL, in which case no distances are returned.

Returns

Number of neighbors within distance of query.

Reimplemented from knncolle::Searcher< Index_, Data_, Distance_ >.

search_all() [2/2]

template<typename Index_ , typename Data_ , typename Distance_ , class DistanceMetric_ >

Index_ knncolle::VptreeSearcher< Index_, Data_, Distance_, DistanceMetric_ >::search_all ( Index_ i, Distance_ distance, std::vector< Index_ > * output_indices, std::vector< Distance_ > * output_distances )

inlinevirtual

Find all neighbors of the i-th observation within a certain distance. This method is optional and may not be implemented by subclasses, so applications should check can_search_all() before attempting a call. A run-time exception is thrown if this method is called on a subclass that does not implement it.

Parameters

	i	The index of the observation of interest. This should be non-negative and less than the total number of observations in Prebuilt::num_observations().
	distance	The distance in which to consider neighbors.
[out]	output_indices	Pointer to a vector, to be filled with the identities of the nearest neighbors in order of increasing distance. This vector is guaranteed to not contain i itself. Optionally NULL, in which case no indices are returned.
[out]	output_distances	Pointer to a vector, to be filled with the distances of the nearest neighbors. This corresponds to the indices reported in output_indices. Optionally NULL, in which case no distances are returned.

Returns

Number of neighbors within distance of i.

Reimplemented from knncolle::Searcher< Index_, Data_, Distance_ >.

---

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

• knncolle/Vptree.hpp