Geometric Near-neighbor Access Tree (GNAT), a data structure for nearest neighbor search. More...
#include <NearestNeighborsGNAT.h>
Classes | |
struct | DataDistCompare |
class | Node |
struct | NodeDistCompare |
Public Member Functions | |
NearestNeighborsGNAT (unsigned int degree=4, unsigned int minDegree=2, unsigned int maxDegree=6, unsigned int maxNumPtsPerLeaf=50, unsigned int removedCacheSize=50) | |
virtual void | setDistanceFunction (const typename NearestNeighbors< _T >::DistanceFunction &distFun) |
Set the distance function to use. | |
virtual void | clear (void) |
Clear the datastructure. | |
virtual void | add (const _T &data) |
Add an element to the datastructure. | |
virtual void | add (const std::vector< _T > &data) |
Add a vector of points. | |
void | rebuildDataStructure () |
Rebuild the internal data structure. | |
virtual bool | remove (const _T &data) |
Remove an element from the datastructure. | |
virtual _T | nearest (const _T &data) const |
Get the nearest neighbor of a point. | |
virtual void | nearestK (const _T &data, std::size_t k, std::vector< _T > &nbh) const |
Get the k-nearest neighbors of a point. | |
virtual void | nearestR (const _T &data, double radius, std::vector< _T > &nbh) const |
Get the nearest neighbors of a point, within a specified radius. | |
virtual std::size_t | size (void) const |
Get the number of elements in the datastructure. | |
virtual void | list (std::vector< _T > &data) const |
Get all the elements in the datastructure. | |
void | integrityCheck () |
Protected Types | |
typedef std::pair< const _T *, double > | DataDist |
typedef std::priority_queue < DataDist, std::vector < DataDist >, DataDistCompare > | NearQueue |
typedef std::pair< Node *, double > | NodeDist |
typedef std::priority_queue < NodeDist, std::vector < NodeDist >, NodeDistCompare > | NodeQueue |
typedef NearestNeighborsGNAT< _T > | GNAT |
Protected Member Functions | |
bool | isRemoved (const _T &data) const |
bool | nearestKInternal (const _T &data, std::size_t k, NearQueue &nbhQueue) const |
void | nearestRInternal (const _T &data, double radius, NearQueue &nbhQueue) const |
void | postprocessNearest (NearQueue &nbhQueue, std::vector< _T > &nbh, unsigned int k=std::numeric_limits< unsigned int >::max()) const |
Protected Attributes | |
Node * | tree_ |
The data elements stored in this structure. | |
unsigned int | degree_ |
unsigned int | minDegree_ |
unsigned int | maxDegree_ |
unsigned int | maxNumPtsPerLeaf_ |
std::size_t | size_ |
std::size_t | removedCacheSize_ |
GreedyKCenters< _T > | pivotSelector_ |
The data structure used to split data into subtrees. | |
boost::unordered_set< const _T * > | removed_ |
Cache of removed elements. | |
Friends | |
std::ostream & | operator<< (std::ostream &out, const NearestNeighborsGNAT< _T > &gnat) |
Geometric Near-neighbor Access Tree (GNAT), a data structure for nearest neighbor search.
See: S. Brin, “Near neighbor search in large metric spaces,” in Proc. 21st Conf. on Very Large Databases (VLDB), pp. 574–584, 1995.
Definition at line 59 of file NearestNeighborsGNAT.h.