rl::math::GnatNearestNeighbors< MetricT > Class Template Reference

Geometric Near-Neighbor Access Tree (GNAT). More...

#include <GnatNearestNeighbors.h>

Classes
struct	BranchCompare
struct	NeighborCompare
struct	Node

Public Types
typedef const MetricT::Value &	const_reference
typedef ::std::ptrdiff_t	difference_type
typedef MetricT::Value &	reference
typedef ::std::size_t	size_type
typedef MetricT::Value	value_type
typedef MetricT::Distance	Distance
typedef MetricT	Metric
typedef MetricT::Value	Value
typedef ::std::pair< Distance, Value >	Neighbor

Public Member Functions
	GnatNearestNeighbors (const Metric &metric)
	GnatNearestNeighbors (Metric &&metric=Metric())
template<typename InputIterator >
	GnatNearestNeighbors (InputIterator first, InputIterator last, const Metric &metric)
template<typename InputIterator >
	GnatNearestNeighbors (InputIterator first, InputIterator last, Metric &&metric=Metric())
	~GnatNearestNeighbors ()
void	clear ()
::std::vector< Value >	data () const
bool	empty () const
::boost::optional< ::std::size_t >	getChecks () const
::std::size_t	getNodeDataMax () const
::std::size_t	getNodeDegree () const
::std::size_t	getNodeDegreeMax () const
::std::size_t	getNodeDegreeMin () const
template<typename InputIterator >
void	insert (InputIterator first, InputIterator last)
::std::vector< Neighbor >	nearest (const Value &query, const ::std::size_t &k, const bool &sorted=true) const
void	push (const Value &value)
::std::vector< Neighbor >	radius (const Value &query, const Distance &radius, const bool &sorted=true) const
void	seed (const ::std::mt19937::result_type &value)
void	setChecks (const ::boost::optional< ::std::size_t > &checks)
void	setNodeDataMax (const ::std::size_t &nodeDataMax)
void	setNodeDegree (const ::std::size_t &nodeDegree)
void	setNodeDegreeMax (const ::std::size_t &nodeDegreeMax)
void	setNodeDegreeMin (const ::std::size_t &nodeDegreeMin)
::std::size_t	size () const
void	swap (GnatNearestNeighbors &other)

Private Types
typedef ::std::pair< Distance, const Node * >	Branch

Private Member Functions
void	choose (const Node &node, ::std::vector< ::std::size_t > &centers, ::std::vector< ::std::vector< Distance >> &distances)
void	data (const Node &node, ::std::vector< Value > &data) const
void	push (Node &node, const Value &value)
::std::vector< Neighbor >	search (const Value &query, const ::std::size_t *k, const Distance *radius, const bool &sorted) const
void	search (const Node &node, const Value &query, const ::std::size_t *k, const Distance *radius, ::std::vector< Branch > &branches, ::std::vector< Neighbor > &neighbors, ::std::size_t &checks) const
void	split (Node &node)

Private Attributes
::boost::optional< ::std::size_t >	checks
::std::mt19937	generator
Metric	metric
::std::size_t	nodeDataMax
::std::size_t	nodeDegree
::std::size_t	nodeDegreeMax
::std::size_t	nodeDegreeMin
Node	root
::std::size_t	values

Friends
void	swap (GnatNearestNeighbors &lhs, GnatNearestNeighbors &rhs)

Detailed Description

template<typename MetricT>
class rl::math::GnatNearestNeighbors< MetricT >

Geometric Near-Neighbor Access Tree (GNAT).

Sergey Brin. Near neighbor search in large metric spaces. In Proceedings of the International Conference on Very Large Data Bases, pages 574-584, Zurich, Switzerland, September, 1985.

http://www.vldb.org/conf/1995/P574.PDF

Member Typedef Documentation

Branch

template<typename MetricT >

typedef ::std::pair<Distance, const Node*> rl::math::GnatNearestNeighbors< MetricT >::Branch

private

const_reference

template<typename MetricT >

typedef const MetricT::Value& rl::math::GnatNearestNeighbors< MetricT >::const_reference

difference_type

template<typename MetricT >

typedef ::std::ptrdiff_t rl::math::GnatNearestNeighbors< MetricT >::difference_type

Distance

template<typename MetricT >

typedef MetricT::Distance rl::math::GnatNearestNeighbors< MetricT >::Distance

Metric

template<typename MetricT >

typedef MetricT rl::math::GnatNearestNeighbors< MetricT >::Metric

Neighbor

template<typename MetricT >

typedef ::std::pair<Distance, Value> rl::math::GnatNearestNeighbors< MetricT >::Neighbor

reference

template<typename MetricT >

typedef MetricT::Value& rl::math::GnatNearestNeighbors< MetricT >::reference

size_type

template<typename MetricT >

typedef ::std::size_t rl::math::GnatNearestNeighbors< MetricT >::size_type

Value

template<typename MetricT >

typedef MetricT::Value rl::math::GnatNearestNeighbors< MetricT >::Value

value_type

template<typename MetricT >

typedef MetricT::Value rl::math::GnatNearestNeighbors< MetricT >::value_type

Constructor & Destructor Documentation

GnatNearestNeighbors() [1/4]

template<typename MetricT >

rl::math::GnatNearestNeighbors< MetricT >::GnatNearestNeighbors ( const Metric &  metric )

inlineexplicit

GnatNearestNeighbors() [2/4]

template<typename MetricT >

rl::math::GnatNearestNeighbors< MetricT >::GnatNearestNeighbors ( Metric &&  metric = Metric() )

inlineexplicit

GnatNearestNeighbors() [3/4]

template<typename MetricT >

template<typename InputIterator >

rl::math::GnatNearestNeighbors< MetricT >::GnatNearestNeighbors ( InputIterator  first, InputIterator  last, const Metric &  metric  )

inline

GnatNearestNeighbors() [4/4]

template<typename MetricT >

template<typename InputIterator >

rl::math::GnatNearestNeighbors< MetricT >::GnatNearestNeighbors ( InputIterator  first, InputIterator  last, Metric &&  metric = Metric()  )

inline

~GnatNearestNeighbors()

template<typename MetricT >

rl::math::GnatNearestNeighbors< MetricT >::~GnatNearestNeighbors ( )

inline

Member Function Documentation

choose()

template<typename MetricT >

void rl::math::GnatNearestNeighbors< MetricT >::choose ( const Node &  node, ::std::vector< ::std::size_t > &  centers, ::std::vector< ::std::vector< Distance >> &  distances  )

inlineprivate

clear()

template<typename MetricT >

void rl::math::GnatNearestNeighbors< MetricT >::clear ( )

inline

data() [1/2]

template<typename MetricT >

::std::vector<Value> rl::math::GnatNearestNeighbors< MetricT >::data ( ) const

inline

data() [2/2]

template<typename MetricT >

void rl::math::GnatNearestNeighbors< MetricT >::data ( const Node &  node, ::std::vector< Value > &  data  ) const

inlineprivate

empty()

template<typename MetricT >

bool rl::math::GnatNearestNeighbors< MetricT >::empty ( ) const

inline

getChecks()

template<typename MetricT >

::boost::optional< ::std::size_t> rl::math::GnatNearestNeighbors< MetricT >::getChecks ( ) const

inline

getNodeDataMax()

template<typename MetricT >

::std::size_t rl::math::GnatNearestNeighbors< MetricT >::getNodeDataMax ( ) const

inline

getNodeDegree()

template<typename MetricT >

::std::size_t rl::math::GnatNearestNeighbors< MetricT >::getNodeDegree ( ) const

inline

getNodeDegreeMax()

template<typename MetricT >

::std::size_t rl::math::GnatNearestNeighbors< MetricT >::getNodeDegreeMax ( ) const

inline

getNodeDegreeMin()

template<typename MetricT >

::std::size_t rl::math::GnatNearestNeighbors< MetricT >::getNodeDegreeMin ( ) const

inline

insert()

template<typename MetricT >

template<typename InputIterator >

void rl::math::GnatNearestNeighbors< MetricT >::insert ( InputIterator  first, InputIterator  last  )

inline

nearest()

template<typename MetricT >

::std::vector<Neighbor> rl::math::GnatNearestNeighbors< MetricT >::nearest ( const Value &  query, const ::std::size_t &  k, const bool &  sorted = true  ) const

inline

push() [1/2]

template<typename MetricT >

void rl::math::GnatNearestNeighbors< MetricT >::push ( const Value &  value )

inline

push() [2/2]

template<typename MetricT >

void rl::math::GnatNearestNeighbors< MetricT >::push ( Node &  node, const Value &  value  )

inlineprivate

radius()

template<typename MetricT >

::std::vector<Neighbor> rl::math::GnatNearestNeighbors< MetricT >::radius ( const Value &  query, const Distance &  radius, const bool &  sorted = true  ) const

inline

search() [1/2]

template<typename MetricT >

void rl::math::GnatNearestNeighbors< MetricT >::search ( const Node &  node, const Value &  query, const ::std::size_t *  k, const Distance *  radius, ::std::vector< Branch > &  branches, ::std::vector< Neighbor > &  neighbors, ::std::size_t &  checks  ) const

inlineprivate

search() [2/2]

template<typename MetricT >

::std::vector<Neighbor> rl::math::GnatNearestNeighbors< MetricT >::search ( const Value &  query, const ::std::size_t *  k, const Distance *  radius, const bool &  sorted  ) const

inlineprivate

seed()

template<typename MetricT >

void rl::math::GnatNearestNeighbors< MetricT >::seed ( const ::std::mt19937::result_type &  value )

inline

setChecks()

template<typename MetricT >

void rl::math::GnatNearestNeighbors< MetricT >::setChecks ( const ::boost::optional< ::std::size_t > &  checks )

inline

setNodeDataMax()

template<typename MetricT >

void rl::math::GnatNearestNeighbors< MetricT >::setNodeDataMax ( const ::std::size_t &  nodeDataMax )

inline

setNodeDegree()

template<typename MetricT >

void rl::math::GnatNearestNeighbors< MetricT >::setNodeDegree ( const ::std::size_t &  nodeDegree )

inline

setNodeDegreeMax()

template<typename MetricT >

void rl::math::GnatNearestNeighbors< MetricT >::setNodeDegreeMax ( const ::std::size_t &  nodeDegreeMax )

inline

setNodeDegreeMin()

template<typename MetricT >

void rl::math::GnatNearestNeighbors< MetricT >::setNodeDegreeMin ( const ::std::size_t &  nodeDegreeMin )

inline

size()

template<typename MetricT >

::std::size_t rl::math::GnatNearestNeighbors< MetricT >::size ( ) const

inline

split()

template<typename MetricT >

void rl::math::GnatNearestNeighbors< MetricT >::split ( Node &  node )

inlineprivate

swap()

template<typename MetricT >

void rl::math::GnatNearestNeighbors< MetricT >::swap ( GnatNearestNeighbors< MetricT > &  other )

inline

Friends And Related Function Documentation

swap

template<typename MetricT >

void swap ( GnatNearestNeighbors< MetricT > &  lhs, GnatNearestNeighbors< MetricT > &  rhs  )

friend

Member Data Documentation

checks

template<typename MetricT >

::boost::optional< ::std::size_t> rl::math::GnatNearestNeighbors< MetricT >::checks

private

generator

template<typename MetricT >

::std::mt19937 rl::math::GnatNearestNeighbors< MetricT >::generator

private

metric

template<typename MetricT >

Metric rl::math::GnatNearestNeighbors< MetricT >::metric

private

nodeDataMax

template<typename MetricT >

::std::size_t rl::math::GnatNearestNeighbors< MetricT >::nodeDataMax

private

nodeDegree

template<typename MetricT >

::std::size_t rl::math::GnatNearestNeighbors< MetricT >::nodeDegree

private

nodeDegreeMax

template<typename MetricT >

::std::size_t rl::math::GnatNearestNeighbors< MetricT >::nodeDegreeMax

private

nodeDegreeMin

template<typename MetricT >

::std::size_t rl::math::GnatNearestNeighbors< MetricT >::nodeDegreeMin

private

root

template<typename MetricT >

Node rl::math::GnatNearestNeighbors< MetricT >::root

private

values

template<typename MetricT >

::std::size_t rl::math::GnatNearestNeighbors< MetricT >::values

private

---

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

• rl/math/GnatNearestNeighbors.h