An efficient algorithm for finding neighbors. Empirically, this class seems to be a little bit slower than GKdTree. More...
#include <GNeighborFinder.h>
Public Member Functions | |
| GBallTree (const GMatrix *pData, size_t neighborCount, GDistanceMetric *pMetric=NULL, bool ownMetric=false) | |
| virtual | ~GBallTree () |
| void | drop (size_t index) |
| Drops the specified index from this ball tree. Throws an exception of the specified index is not found in the tree. Note that the tree still assumes that the other indexes still retain their relationship with the points in the dataset that was used to construct this object, so you should not move the rows in that dataset around. Also note that before you call reoptimize, you need to delete any rows that were dropped, or else they will then be added back in. More... | |
| void | dropAll () |
| Drops all of the leaf point indexes, but retains the interior structure. (This might be useful if you know in advance which points will be inserted, but you don't want them to be in the tree yet.) More... | |
| void | insert (size_t index) |
| Inserts a new point into this ball tree. This method assumes you have already added a new row to the dataset that was used to construct this tree. Calling this method informs this structure that it should also index the new point. Note that this method may reduce the efficiency of the tree by a small amount, so you might want to call reoptimize after several points are added. More... | |
| virtual void | neighbors (size_t *pOutNeighbors, size_t index) |
| See the comment for GNeighborFinder::neighbors. More... | |
| virtual void | neighbors (size_t *pOutNeighbors, double *pOutDistances, size_t index) |
| See the comment for GNeighborFinder::neighbors. More... | |
| virtual void | neighbors (size_t *pOutNeighbors, double *pOutDistances, const double *pInputVector) |
| See the comment for GNeighborFinderGeneralizing::neighbors. More... | |
| virtual void | reoptimize () |
| Rebuilds the tree to improve subsequent performance. This should be called after a significant number of point-vectors are added to or released from the internal set. More... | |
| void | setMaxLeafSize (size_t n) |
| Specify the max number of point-vectors to store in each leaf node. More... | |
 Public Member Functions inherited from GClasses::GNeighborFinderGeneralizing | |
| GNeighborFinderGeneralizing (const GMatrix *pData, size_t neighborCount, GDistanceMetric *pMetric=NULL, bool ownMetric=false) | |
| Create a neighborfinder for finding the neighborCount nearest neighbors under the given metric. If ownMetric is true, then the neighborFinder takes responsibility for deleting the metric, otherwise it is the caller's responsibility. More... | |
| virtual | ~GNeighborFinderGeneralizing () |
| virtual bool | canGeneralize () |
| Returns true. See the comment for GNeighborFinder::canGeneralize. More... | |
| Public Member Functions inherited from GClasses::GNeighborFinder | |
| GNeighborFinder (const GMatrix *pData, size_t neighborCount) | |
| virtual | ~GNeighborFinder () |
| const GMatrix * | data () |
| Returns the data passed to the constructor of this object. More... | |
| virtual bool | isCached () |
| Returns true iff the neighbors and distances are pre-computed. More... | |
| size_t | neighborCount () |
| Returns the number of neighbors to find. More... | |
| void | sortNeighbors (size_t *pNeighbors, double *pDistances) |
| Uses Quick Sort to sort the neighbors from least to most dissimilar, followed by any slots for with INVALID_INDEX for the index. (Note: This method is pointless, since the neighors are already guaranteed to come in sorted order. Todo: figure out why it is still here) More... | |
Static Public Member Functions | |
| static void | test () |
| Performs unit tests for this class. Throws an exception if there is a failure. More... | |
| Static Public Member Functions inherited from GClasses::GNeighborFinder | |
| static void | sortNeighbors (size_t neighborCount, size_t *pNeighbors, double *pDistances) |
| Uses Quick Sort to sort the neighbors from least to most dissimilar, followed by any slots for with INVALID_INDEX for the index. (Note: This method is pointless, since the neighors are already guaranteed to come in sorted order. Todo: figure out why it is still here) More... | |
Protected Member Functions | |
| GBallNode * | buildTree (size_t count, size_t *pIndexes) |
| Build the tree. More... | |
| void | findNeighbors (size_t *pOutNeighbors, double *pOutDistances, const double *pInputVector, size_t nExclude) |
| This is the helper method that finds the neighbors. More... | |
Protected Attributes | |
| size_t | m_maxLeafSize |
| GBallNode * | m_pRoot |
| size_t | m_size |
| Protected Attributes inherited from GClasses::GNeighborFinderGeneralizing | |
| bool | m_ownMetric |
| GDistanceMetric * | m_pMetric |
| Protected Attributes inherited from GClasses::GNeighborFinder | |
| size_t | m_neighborCount |
| const GMatrix * | m_pData |
Detailed Description
An efficient algorithm for finding neighbors. Empirically, this class seems to be a little bit slower than GKdTree.
Constructor & Destructor Documentation
| GClasses::GBallTree::GBallTree | ( | const GMatrix * | pData, |
| size_t | neighborCount, | ||
| GDistanceMetric * | pMetric = NULL, |
||
| bool | ownMetric = false |
||
| ) |
|
virtual |
Member Function Documentation
|
protected |
Build the tree.
| void GClasses::GBallTree::drop | ( | size_t | index | ) |
Drops the specified index from this ball tree. Throws an exception of the specified index is not found in the tree. Note that the tree still assumes that the other indexes still retain their relationship with the points in the dataset that was used to construct this object, so you should not move the rows in that dataset around. Also note that before you call reoptimize, you need to delete any rows that were dropped, or else they will then be added back in.
| void GClasses::GBallTree::dropAll | ( | ) |
Drops all of the leaf point indexes, but retains the interior structure. (This might be useful if you know in advance which points will be inserted, but you don't want them to be in the tree yet.)
|
protected |
This is the helper method that finds the neighbors.
| void GClasses::GBallTree::insert | ( | size_t | index | ) |
Inserts a new point into this ball tree. This method assumes you have already added a new row to the dataset that was used to construct this tree. Calling this method informs this structure that it should also index the new point. Note that this method may reduce the efficiency of the tree by a small amount, so you might want to call reoptimize after several points are added.
|
virtual |
See the comment for GNeighborFinder::neighbors.
Implements GClasses::GNeighborFinder.
|
virtual |
See the comment for GNeighborFinder::neighbors.
Implements GClasses::GNeighborFinder.
|
virtual |
See the comment for GNeighborFinderGeneralizing::neighbors.
Implements GClasses::GNeighborFinderGeneralizing.
|
virtual |
Rebuilds the tree to improve subsequent performance. This should be called after a significant number of point-vectors are added to or released from the internal set.
Implements GClasses::GNeighborFinderGeneralizing.
|
inline |
Specify the max number of point-vectors to store in each leaf node.
|
static |
Performs unit tests for this class. Throws an exception if there is a failure.
Member Data Documentation
|
protected |
|
protected |
|
protected |
