NearestNeighborsGNATNoThreadSafety.h
94 , rebuildSize_(rebalancing ? maxNumPtsPerLeaf * degree : std::numeric_limits<std::size_t>::max())
109 void setDistanceFunction(const typename NearestNeighbors<_T>::DistanceFunction &distFun) override
230 {
263 friend std::ostream &operator<<(std::ostream &out, const NearestNeighborsGNATNoThreadSafety<_T> &gnat)
277 }
302 assert(i != lst.size());
359 if (node->distToPivot_ > node->maxRadius_ + dist || node->distToPivot_ < node->minRadius_ - dist)
389 #endif
443 gnat.rebuildDataStructure();
530 bool insertNeighborK(NearQueue &nbh, std::size_t k, const _T &data, const _T &key, double dist) const
594 }
660 }
666 }
Random number generation. An instance of this class cannot be used by multiple threads at once (membe...
Definition: RandomNumbers.h:89
NodeQueue nodeQueue_
Nodes yet to be processed for possible nearest neighbors.
Definition: NearestNeighborsGNATNoThreadSafety.h:857
Eigen::MatrixXd Matrix
A matrix type for storing distances between points and centers.
Definition: GreedyKCenters.h:120
void insertNeighborR(NearQueue &nbh, double r, const _T &data, double dist) const
Insert data in nbh if it is a near neighbor.
Definition: NearestNeighborsGNATNoThreadSafety.h:660
std::unordered_set< const _T * > removed_
Cache of removed elements.
Definition: NearestNeighborsGNATNoThreadSafety.h:850
bool needToSplit(const GNAT &gnat) const
Return true iff the node needs to be split into child nodes.
Definition: NearestNeighborsGNATNoThreadSafety.h:535
friend std::ostream & operator<<(std::ostream &out, const NearestNeighborsGNATNoThreadSafety< _T > &gnat)
Print a GNAT structure (mostly useful for debugging purposes).
Definition: NearestNeighborsGNATNoThreadSafety.h:327
std::size_t removedCacheSize_
Maximum number of removed elements that can be stored in the removed_ cache. If the cache is full,...
Definition: NearestNeighborsGNATNoThreadSafety.h:846
bool remove(const _T &data) override
Remove data from the tree. The element won't actually be removed immediately, but just marked for rem...
Definition: NearestNeighborsGNATNoThreadSafety.h:242
void updateRadius(double dist)
Update minRadius_ and maxRadius_, given that an element was added with distance dist to the pivot.
Definition: NearestNeighborsGNATNoThreadSafety.h:467
void permute(unsigned int n)
Create a permutation of the numbers 0, ..., n - 1.
Definition: Permutation.h:122
void nearestR(const GNAT &gnat, const _T &data, double r) const
Return all elements that are within distance r in nbh.
Definition: NearestNeighborsGNATNoThreadSafety.h:666
std::vector< double > maxRange_
The i-th element in maxRange_ is the maximum distance between the pivot and any data_ element in the ...
Definition: NearestNeighborsGNATNoThreadSafety.h:786
Geometric Near-neighbor Access Tree (GNAT), a data structure for nearest neighbor search.
Definition: NearestNeighborsGNATNoThreadSafety.h:103
void add(GNAT &gnat, const _T &data)
Add an element to the tree rooted at this node.
Definition: NearestNeighborsGNATNoThreadSafety.h:495
void setDistanceFunction(const typename NearestNeighbors< _T >::DistanceFunction &distFun) override
Set the distance function to use.
Definition: NearestNeighborsGNATNoThreadSafety.h:173
An instance of this class can be used to greedily select a given number of representatives from a set...
Definition: GreedyKCenters.h:82
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: NearestNeighborsGNATNoThreadSafety.h:487
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: NearestNeighborsGNATNoThreadSafety.h:594
const _T pivot_
Data element stored in this Node.
Definition: NearestNeighborsGNATNoThreadSafety.h:776
void nearestK(const _T &data, std::size_t k, std::vector< _T > &nbh) const override
Return the k nearest neighbors in sorted order.
Definition: NearestNeighborsGNATNoThreadSafety.h:277
GreedyKCenters< _T > pivotSelector_
The data structure used to split data into subtrees.
Definition: NearestNeighborsGNATNoThreadSafety.h:848
void nearestR(const _T &data, double radius, std::vector< _T > &nbh) const override
Return the nearest neighbors within distance radius in sorted order.
Definition: NearestNeighborsGNATNoThreadSafety.h:290
std::vector< double > minRange_
The i-th element in minRange_ is the minimum distance between the pivot and any data_ element in the ...
Definition: NearestNeighborsGNATNoThreadSafety.h:783
unsigned int maxDegree_
After splitting a Node, each child Node has degree equal to the default degree times the fraction of ...
Definition: NearestNeighborsGNATNoThreadSafety.h:834
double maxRadius_
Maximum distance between the pivot element and the elements stored in data_.
Definition: NearestNeighborsGNATNoThreadSafety.h:780
std::function< double(const _T &, const _T &)> DistanceFunction
The definition of a distance function.
Definition: NearestNeighbors.h:115
std::size_t size_
Number of elements stored in the tree.
Definition: NearestNeighborsGNATNoThreadSafety.h:839
unsigned int minDegree_
After splitting a Node, each child Node has degree equal to the default degree times the fraction of ...
Definition: NearestNeighborsGNATNoThreadSafety.h:829
Node(int degree, int capacity, _T pivot)
Construct a node of given degree with at most capacity data elements and with given pivot.
Definition: NearestNeighborsGNATNoThreadSafety.h:443
std::vector< _T > data_
The data elements stored in this node (in addition to the pivot element). An internal node has no ele...
Definition: NearestNeighborsGNATNoThreadSafety.h:789
bool nearestKInternal(const _T &data, std::size_t k) const
Return in nearQueue_ the k nearest neighbors of data. For k=1, return true if the nearest neighbor is...
Definition: NearestNeighborsGNATNoThreadSafety.h:389
Node * tree_
The data structure containing the elements stored in this structure.
Definition: NearestNeighborsGNATNoThreadSafety.h:822
void add(const _T &data) override
Add an element to the datastructure.
Definition: NearestNeighborsGNATNoThreadSafety.h:199
void nearestRInternal(const _T &data, double radius) const
Return in nearQueue_ the elements that are within distance radius of data.
Definition: NearestNeighborsGNATNoThreadSafety.h:411
std::size_t rebuildSize_
If size_ exceeds rebuildSize_, the tree will be rebuilt (and automatically rebalanced),...
Definition: NearestNeighborsGNATNoThreadSafety.h:842
unsigned int maxNumPtsPerLeaf_
Maximum number of elements allowed to be stored in a Node before it needs to be split into several no...
Definition: NearestNeighborsGNATNoThreadSafety.h:837
unsigned int degree_
The desired degree of each node.
Definition: NearestNeighborsGNATNoThreadSafety.h:824
double minRadius_
Minimum distance between the pivot element and the elements stored in data_.
Definition: NearestNeighborsGNATNoThreadSafety.h:778
bool reportsSortedResults() const override
Return true if the solutions reported by this data structure are sorted, when calling nearestK / near...
Definition: NearestNeighborsGNATNoThreadSafety.h:194
void nearestK(const GNAT &gnat, const _T &data, std::size_t k, bool &isPivot) const
Compute the k nearest neighbors of data in the tree. For k=1, isPivot is true if the nearest neighbor...
Definition: NearestNeighborsGNATNoThreadSafety.h:614
Permutation permutation_
Permutation of indices to process children of a node in random order.
Definition: NearestNeighborsGNATNoThreadSafety.h:859
void postprocessNearest(std::vector< _T > &nbh) const
Convert the internal data structure used for storing neighbors to the vector that NearestNeighbor API...
Definition: NearestNeighborsGNATNoThreadSafety.h:430
void split(GNAT &gnat)
The split operation finds pivot elements for the child nodes and moves each data element of this node...
Definition: NearestNeighborsGNATNoThreadSafety.h:543
std::size_t size() const override
Get the number of elements in the datastructure.
Definition: NearestNeighborsGNATNoThreadSafety.h:302
bool isRemoved(const _T &data) const
Return true iff data has been marked for removal.
Definition: NearestNeighborsGNATNoThreadSafety.h:381
double distToPivot_
Scratch space to store distance to pivot during nearest neighbor queries.
Definition: NearestNeighborsGNATNoThreadSafety.h:795
void rebuildDataStructure()
Rebuild the internal data structure.
Definition: NearestNeighborsGNATNoThreadSafety.h:230
std::vector< Node * > children_
The child nodes of this node. By definition, only internal nodes have child nodes.
Definition: NearestNeighborsGNATNoThreadSafety.h:792
GreedyKCenters< _T >::Matrix distances_
Matrix of distances to pivots.
Definition: NearestNeighborsGNATNoThreadSafety.h:863
_T nearest(const _T &data) const override
Get the nearest neighbor of a point.
Definition: NearestNeighborsGNATNoThreadSafety.h:261
std::vector< unsigned int > pivots_
Pivot indices within a vector of elements as selected by GreedyKCenters.
Definition: NearestNeighborsGNATNoThreadSafety.h:861
void list(std::vector< _T > &data) const override
Get all the elements in the datastructure.
Definition: NearestNeighborsGNATNoThreadSafety.h:318
virtual void setDistanceFunction(const DistanceFunction &distFun)
Set the distance function to use.
Definition: NearestNeighbors.h:122
The class used internally to define the GNAT.
Definition: NearestNeighborsGNATNoThreadSafety.h:438