shark::IterativeNNQuery< DataContainer > Class Template Reference

Iterative nearest neighbors query. More...

#include <shark/Algorithms/NearestNeighbors/TreeNearestNeighbors.h>

Public Member Functions
	IterativeNNQuery (tree_type const *tree, DataContainer const &data, value_type const &point)
	~IterativeNNQuery ()
	destroy the query object and its internal data structures More...
std::size_t	neighbors () const
	return the number of neighbors already found More...
result_type	next ()
	find and return the next nearest neighbor More...
std::size_t	queuesize () const

Detailed Description

template<class DataContainer>
class shark::IterativeNNQuery< DataContainer >

Iterative nearest neighbors query.

The IterativeNNQuery class (Iterative Nearest Neighbor Query) allows the nearest neighbors of a reference point to be queried iteratively. Given the reference point, a query is set up that returns the nearest neighbor first, then the second nearest neighbor, and so on. Thus, nearest neighbor queries are treated in an "online" fashion. The algorithm follows the paper (generalized to arbitrary space-partitioning trees):

Strategies for efficient incremental nearest neighbor search. A. J. Broder. Pattern Recognition 23(1/2), pp 171-178, 1990.

The algorithm is based on traversing a BinaryTree that partitions the space into nested cells. The triangle inequality is applied to exclude cells from the search. Furthermore, candidate points are cached in a queue, such that subsequent queries profit from points that could not be excluded this way, but that did not turn out the be the (current) nearest neighbor.

The tree must have a bucket size of one, but leaf nodes with multiple copies of the same point are allowed. This means that the space partitioning must be carried out to the finest possible scale.

The Data must be sotred in a random access container. This means that elements have O(1) access time. This is crucial for the performance of the tree lookup. When data is stored in a Data<T>, a View should be chosen as template parameter.

Definition at line 82 of file TreeNearestNeighbors.h.

Constructor & Destructor Documentation

IterativeNNQuery()

template<class DataContainer>

shark::IterativeNNQuery< DataContainer >::IterativeNNQuery ( tree_type const *  tree, DataContainer const &  data, value_type const &  point  )

inline

create a new query

Parameters

tree	Underlying space-partitioning tree (this is assumed to persist for the lifetime of the query object).
data	Container holding the stored data which is referenced by the tree
point	Point whose nearest neighbors are to be found.

Definition at line 94 of file TreeNearestNeighbors.h.

References shark::BinaryTree< InputT >::hasChildren(), shark::BinaryTree< InputT >::isLeft(), shark::BinaryTree< InputT >::left(), and shark::BinaryTree< InputT >::right().

~IterativeNNQuery()

template<class DataContainer>

shark::IterativeNNQuery< DataContainer >::~IterativeNNQuery ( )

inline

destroy the query object and its internal data structures

Definition at line 122 of file TreeNearestNeighbors.h.

Member Function Documentation

neighbors()

template<class DataContainer>

std::size_t shark::IterativeNNQuery< DataContainer >::neighbors ( ) const

inline

return the number of neighbors already found

Definition at line 129 of file TreeNearestNeighbors.h.

next()

template<class DataContainer>

result_type shark::IterativeNNQuery< DataContainer >::next ( )

inline

find and return the next nearest neighbor

Definition at line 134 of file TreeNearestNeighbors.h.

References SHARK_RUNTIME_CHECK.

queuesize()

template<class DataContainer>

std::size_t shark::IterativeNNQuery< DataContainer >::queuesize ( ) const

inline

return the size of the queue, which is a measure of the overhead of the search

Definition at line 169 of file TreeNearestNeighbors.h.

References shark::BinaryTree< InputT >::hasChildren(), shark::BinaryTree< InputT >::left(), shark::NONE, shark::BinaryTree< InputT >::right(), and shark::BinaryTree< InputT >::squaredDistanceLowerBound().

---

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

• include/shark/Algorithms/NearestNeighbors/TreeNearestNeighbors.h