knncolle::NeighborQueue< Index_, Distance_ > Class Template Reference

Helper class to track nearest neighbors. More...

#include <NeighborQueue.hpp>

Public Member Functions
	NeighborQueue ()=default
void	reset (Index_ k)
bool	is_full () const
Distance_	limit () const
void	add (Index_ i, Distance_ d)
void	report (std::vector< Index_ > *output_indices, std::vector< Distance_ > *output_distances, Index_ self)
void	report (std::vector< Index_ > *output_indices, std::vector< Distance_ > *output_distances)

Detailed Description

template<typename Index_, typename Distance_>
class knncolle::NeighborQueue< Index_, Distance_ >

Helper class to track nearest neighbors.

This is a priority queue that tracks the nearest neighbors of an observation of interest. Specifically, it contains indices and distances of the k nearest neighbors, in decreasing order from the top of the queue. When the queue is at capacity and new elements are added, existing elements will be displaced by incoming elements with shorter distances.

This class is intended to be used in implementations of Searcher::search() to track the k-nearest neighbors. When searching for neighbors of an existing observation in the dataset, it is recommended to search for the k + 1 neighbors. The appropriate report() overload can then be used to remove the observation of interest from its own neighbor list.

Template Parameters

Index_	Integer type for the observation indices.
Distance_	Floating point type for the distances.

Constructor & Destructor Documentation

NeighborQueue()

template<typename Index_ , typename Distance_ >

knncolle::NeighborQueue< Index_, Distance_ >::NeighborQueue ( )

default

Default constructor. The maximum number of neighbors to be retained is 1; this can be changed by reset().

Member Function Documentation

add()

template<typename Index_ , typename Distance_ >

void knncolle::NeighborQueue< Index_, Distance_ >::add ( Index_ i, Distance_ d )

inline

Attempt to add a neighbor to the queue. This will be a no-op if is_full() is true and d > limit().

Parameters

i	Index of the neighbor.
d	Distance to the neighbor.

is_full()

template<typename Index_ , typename Distance_ >

bool knncolle::NeighborQueue< Index_, Distance_ >::is_full ( ) const

inline

Returns

Whether the queue is full.

limit()

template<typename Index_ , typename Distance_ >

Distance_ knncolle::NeighborQueue< Index_, Distance_ >::limit ( ) const

inline

Returns

The distance of the k-th furthest neighbor, where k is the number of neighbors in reset(). This should only be called if is_full() returns true.

report() [1/2]

template<typename Index_ , typename Distance_ >

void knncolle::NeighborQueue< Index_, Distance_ >::report ( std::vector< Index_ > * output_indices, std::vector< Distance_ > * output_distances )

inline

Report the indices and distances of the nearest neighbors in the queue. It is assumed that the observation of interest is not detected as its own neighbor, presumably as it does not exist in the original input dataset.

Parameters

[out]	output_indices	Pointer to a vector in which to store the indices of the nearest neighbors, sorted by distance. If NULL, the indices will not be reported.
[out]	output_distances	Pointer to a vector in which to store the (sorted) distances to the nearest neighbors. If NULL, the distances will not be reported. Otherwise, on output, this will have the same length as *output_indices and contain distances to each of those neighbors.

report() [2/2]

template<typename Index_ , typename Distance_ >

void knncolle::NeighborQueue< Index_, Distance_ >::report ( std::vector< Index_ > * output_indices, std::vector< Distance_ > * output_distances, Index_ self )

inline

Report the indices and distances of the nearest neighbors in the queue. If the observation of interest is detected as its own neighbor, it will be removed from the output vectors.

Parameters

[out]	output_indices	Pointer to a vector in which to store the indices of the nearest neighbors, sorted by distance. If NULL, the indices will not be reported.
[out]	output_distances	Pointer to a vector in which to store the (sorted) distances to the nearest neighbors. If NULL, the distances will not be reported. Otherwise, on output, this will have the same length as *output_indices and contain distances to each of those neighbors.
	self	Index of the observation of interest, i.e., for which neighbors are to be identified. If present in the queue, this will be removed from output_indices and output_distances.

reset()

template<typename Index_ , typename Distance_ >

void knncolle::NeighborQueue< Index_, Distance_ >::reset ( Index_ k )

inline

Resets the queue to retain k neighbors. Any existing neighbors in the queue are removed.

Parameters

k	Maximum number of neighbors to retain. This should be a positive integer.

---

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

• knncolle/NeighborQueue.hpp