Interface for searching nearest-neighbor search indices. More...

#include <Searcher.hpp>

Inheritance diagram for knncolle::Searcher< Index_, Data_, Distance_ >:

[legend]

Public Member Functions
virtual void	search (Index_ i, Index_ k, std::vector< Index_ > output_indices, std::vector< Distance_ > output_distances)=0

virtual void	search (const Data_ query, Index_ k, std::vector< Index_ > output_indices, std::vector< Distance_ > *output_distances)=0

virtual bool	can_search_all () const

virtual Index_	search_all (Index_ i, Distance_ distance, std::vector< Index_ > output_indices, std::vector< Distance_ > output_distances)

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

Detailed Description

template<typename Index_, typename Data_, typename Distance_>
class knncolle::Searcher< Index_, Data_, Distance_ >

Interface for searching nearest-neighbor search indices.

Instances of Searcher subclasses are typically constructed with Prebuilt::initialize(). This is intended to allow re-use of data allocations across different calls to search(). Users should ensure that a Searcher instance does not outlive the Prebuilt object used to generate it; this allows developers of the former to hold references to the latter.

Template Parameters

Index_	Integer type for the observation indices.
Data_	Numeric type for the query data.
Distance_	Floating point type for the distances.

Member Function Documentation

◆ can_search_all()

template<typename Index_ , typename Data_ , typename Distance_ >

virtual bool knncolle::Searcher< Index_, Data_, Distance_ >::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 in knncolle::BruteforceSearcher< Index_, Data_, Distance_, DistanceMetric_ >, and knncolle::VptreeSearcher< Index_, Data_, Distance_, DistanceMetric_ >.

◆ search() [1/2]

template<typename Index_ , typename Data_ , typename Distance_ >

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

pure virtual

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()`. Users can call `cap_k_query()` 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()`. 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.

Implemented in knncolle::BruteforceSearcher< Index_, Data_, Distance_, DistanceMetric_ >, and knncolle::VptreeSearcher< Index_, Data_, Distance_, DistanceMetric_ >.

◆ search() [2/2]

template<typename Index_ , typename Data_ , typename Distance_ >

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

pure virtual

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.

Implemented in knncolle::BruteforceSearcher< Index_, Data_, Distance_, DistanceMetric_ >, and knncolle::VptreeSearcher< Index_, Data_, Distance_, DistanceMetric_ >.

◆ search_all() [1/2]

template<typename Index_ , typename Data_ , typename Distance_ >

virtual Index_ knncolle::Searcher< Index_, Data_, Distance_ >::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 in knncolle::BruteforceSearcher< Index_, Data_, Distance_, DistanceMetric_ >, and knncolle::VptreeSearcher< Index_, Data_, Distance_, DistanceMetric_ >.

◆ search_all() [2/2]

template<typename Index_ , typename Data_ , typename Distance_ >

virtual Index_ knncolle::Searcher< Index_, Data_, Distance_ >::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 in knncolle::BruteforceSearcher< Index_, Data_, Distance_, DistanceMetric_ >, and knncolle::VptreeSearcher< Index_, Data_, Distance_, DistanceMetric_ >.

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

knncolle/Searcher.hpp

Public Member Functions

Detailed Description

Member Function Documentation

◆ can_search_all()

◆ search() [1/2]

◆ search() [2/2]

◆ search_all() [1/2]

◆ search_all() [2/2]