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. (In the presence of ties, neighbors with lower indices will prevail.)
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_ | Numeric type for the distances, usually floating-point. |
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, excluding the observation of interest self. Specifically, if the observation of interest (self) is detected as its own neighbor, it will be excluded from the output vectors. If self is not found in the set of nearest neighbors (e.g., > k tied points at zero distance), the furthest neighbor will be excluded instead.
This method will report size() - 1 neighbors in the output vectors and thus should only be called if size() > 0.
- 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. |
1.12.0