NearestNeighborsGNAT.h
125 virtual void setDistanceFunction(const typename NearestNeighbors<_T>::DistanceFunction &distFun)
542 bool insertNeighborK(NearQueue& nbh, std::size_t k, const _T& data, const _T& key, double dist) const
623 void nearestR(const GNAT& gnat, const _T &data, double r, NearQueue& nbh, NodeQueue& nodeQueue) const
std::vector< double > maxRange_
The i-th element in maxRange_ is the maximum distance between the pivot and any data_ element in the ...
Definition: NearestNeighborsGNAT.h:746
std::vector< _T > data_
The data elements stored in this node (in addition to the pivot element). An internal node has no ele...
Definition: NearestNeighborsGNAT.h:749
virtual std::size_t size() const
Get the number of elements in the datastructure.
Definition: NearestNeighborsGNAT.h:248
virtual void nearestR(const _T &data, double radius, std::vector< _T > &nbh) const
Return the nearest neighbors within distance radius in sorted order.
Definition: NearestNeighborsGNAT.h:237
unsigned int maxNumPtsPerLeaf_
Maximum number of elements allowed to be stored in a Node before it needs to be split into several no...
Definition: NearestNeighborsGNAT.h:780
void updateRadius(double dist)
Update minRadius_ and maxRadius_, given that an element was added with distance dist to the pivot...
Definition: NearestNeighborsGNAT.h:415
An instance of this class can be used to greedily select a given number of representatives from a set...
Definition: GreedyKCenters.h:48
boost::function< double(const _T &, const _T &)> DistanceFunction
The definition of a distance function.
Definition: NearestNeighbors.h:55
void add(GNAT &gnat, const _T &data)
Add an element to the tree rooted at this node.
Definition: NearestNeighborsGNAT.h:443
bool nearestKInternal(const _T &data, std::size_t k, NearQueue &nbhQueue) const
Return in nbhQueue the k nearest neighbors of data. For k=1, return true if the nearest neighbor is a...
Definition: NearestNeighborsGNAT.h:335
virtual void setDistanceFunction(const typename NearestNeighbors< _T >::DistanceFunction &distFun)
Set the distance function to use.
Definition: NearestNeighborsGNAT.h:125
void insertNeighborR(NearQueue &nbh, double r, const _T &data, double dist) const
Insert data in nbh if it is a near neighbor.
Definition: NearestNeighborsGNAT.h:615
STL namespace.
double minRadius_
Minimum distance between the pivot element and the elements stored in data_.
Definition: NearestNeighborsGNAT.h:738
Geometric Near-neighbor Access Tree (GNAT), a data structure for nearest neighbor search...
Definition: NearestNeighborsGNAT.h:70
void rebuildDataStructure()
Rebuild the internal data structure.
Definition: NearestNeighborsGNAT.h:183
void nearestK(const GNAT &gnat, const _T &data, std::size_t k, NearQueue &nbh, NodeQueue &nodeQueue, bool &isPivot) const
Compute the k nearest neighbors of data in the tree. For k=1, isPivot is true if the nearest neighbor...
Definition: NearestNeighborsGNAT.h:564
unsigned int maxDegree_
After splitting a Node, each child Node has degree equal to the default degree times the fraction of ...
Definition: NearestNeighborsGNAT.h:777
void split(GNAT &gnat)
The split operation finds pivot elements for the child nodes and moves each data element of this node...
Definition: NearestNeighborsGNAT.h:492
unsigned int minDegree_
After splitting a Node, each child Node has degree equal to the default degree times the fraction of ...
Definition: NearestNeighborsGNAT.h:772
Random number generation. An instance of this class cannot be used by multiple threads at once (membe...
Definition: RandomNumbers.h:54
void nearestR(const GNAT &gnat, const _T &data, double r, NearQueue &nbh, NodeQueue &nodeQueue) const
Return all elements that are within distance r in nbh. The nodeQueue, which contains other Nodes that...
Definition: NearestNeighborsGNAT.h:623
virtual _T nearest(const _T &data) const
Get the nearest neighbor of a point.
Definition: NearestNeighborsGNAT.h:212
virtual void setDistanceFunction(const DistanceFunction &distFun)
Set the distance function to use.
Definition: NearestNeighbors.h:66
virtual void nearestK(const _T &data, std::size_t k, std::vector< _T > &nbh) const
Return the k nearest neighbors in sorted order.
Definition: NearestNeighborsGNAT.h:224
virtual void list(std::vector< _T > &data) const
Get all the elements in the datastructure.
Definition: NearestNeighborsGNAT.h:264
void nearestRInternal(const _T &data, double radius, NearQueue &nbhQueue) const
Return in nbhQueue the elements that are within distance radius of data.
Definition: NearestNeighborsGNAT.h:359
virtual void add(const _T &data)
Add an element to the datastructure.
Definition: NearestNeighborsGNAT.h:151
void updateRange(unsigned int i, double dist)
Update minRange_[i] and maxRange_[i], given that an element was added to the i-th child of the parent...
Definition: NearestNeighborsGNAT.h:435
GreedyKCenters< _T > pivotSelector_
The data structure used to split data into subtrees.
Definition: NearestNeighborsGNAT.h:791
virtual bool reportsSortedResults() const
Return true if the solutions reported by this data structure are sorted, when calling nearestK / near...
Definition: NearestNeighborsGNAT.h:146
std::size_t rebuildSize_
If size_ exceeds rebuildSize_, the tree will be rebuilt (and automatically rebalanced), and rebuildSize_ will be doubled.
Definition: NearestNeighborsGNAT.h:785
Abstract representation of a container that can perform nearest neighbors queries.
Definition: NearestNeighbors.h:50
Element * add(const _T &d, const double w)
Adds a piece of data with a given weight to the PDF. Returns a corresponding Element, which can be used to subsequently update or remove the data from the PDF.
Definition: PDF.h:97
std::vector< double > minRange_
The i-th element in minRange_ is the minimum distance between the pivot and any data_ element in the ...
Definition: NearestNeighborsGNAT.h:743
boost::unordered_set< const _T * > removed_
Cache of removed elements.
Definition: NearestNeighborsGNAT.h:793
bool isRemoved(const _T &data) const
Return true iff data has been marked for removal.
Definition: NearestNeighborsGNAT.h:326
bool insertNeighborK(NearQueue &nbh, std::size_t k, const _T &data, const _T &key, double dist) const
Insert data in nbh if it is a near neighbor. Return true iff data was added to nbh.
Definition: NearestNeighborsGNAT.h:542
void postprocessNearest(NearQueue &nbhQueue, std::vector< _T > &nbh) const
Convert the internal data structure used for storing neighbors to the vector that NearestNeighbor API...
Definition: NearestNeighborsGNAT.h:380
Node * tree_
The data structure containing the elements stored in this structure.
Definition: NearestNeighborsGNAT.h:765
The class used internally to define the GNAT.
Definition: NearestNeighborsGNAT.h:389
std::vector< Node * > children_
The child nodes of this node. By definition, only internal nodes have child nodes.
Definition: NearestNeighborsGNAT.h:752
double maxRadius_
Maximum distance between the pivot element and the elements stored in data_.
Definition: NearestNeighborsGNAT.h:740
int uniformInt(int lower_bound, int upper_bound)
Generate a random integer within given bounds: [lower_bound, upper_bound].
Definition: RandomNumbers.h:75
virtual void add(const std::vector< _T > &data)
Add a vector of points.
Definition: NearestNeighborsGNAT.h:165
_T & sample(double r) const
Returns a piece of data from the PDF according to the input sampling value, which must be between 0 a...
Definition: PDF.h:132
std::size_t removedCacheSize_
Maximum number of removed elements that can be stored in the removed_ cache. If the cache is full...
Definition: NearestNeighborsGNAT.h:789
Node(int degree, int capacity, const _T &pivot)
Construct a node of given degree with at most capacity data elements and with given pivot...
Definition: NearestNeighborsGNAT.h:394
bool needToSplit(const GNAT &gnat) const
Return true iff the node needs to be split into child nodes.
Definition: NearestNeighborsGNAT.h:484