Detailed Description

An efficient algorithm for finding neighbors. Empirically, this class seems to be a little bit slower than GKdTree.

#include <GNeighborFinder.h>

Inheritance diagram for GClasses::GBallTree:

Public Member Functions
	GBallTree (const GMatrix pData, 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...

virtual size_t	findNearest (size_t k, size_t index)
	See the comment for GNeighborFinder::findNearest. More...

virtual size_t	findNearest (size_t k, const GVec &vec)
	See the comment for GNeighborFinderGeneralizing::neighbors. More...

virtual size_t	findWithinRadius (double squaredRadius, size_t index)
	See the comment for GNeighborFinder::findWithinRadius. More...

virtual size_t	findWithinRadius (double squaredRadius, const GVec &vec)
	See the comment for GNeighborFinderGeneralizing::findWithinRadius. 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	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, 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...

virtual double	distance (size_t i)
	See the comment for GNeighborFinder::distance. More...

GDistanceMetric *	metric ()
	Returns the metric. More...

virtual size_t	neighbor (size_t i)
	See the comment for GNeighborFinder::neighbor. More...

void	sortNeighbors (size_t start=0, size_t end=INVALID_INDEX)
	Uses Quick Sort to sort the neighbors from least to most distant. More...

Public Member Functions inherited from GClasses::GNeighborFinder
	GNeighborFinder (const GMatrix *pData)

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...

Static Public Member Functions
static void	test ()
	Performs unit tests for this class. Throws an exception if there is a failure. More...

Protected Member Functions
GBallNode *	buildTree (size_t count, size_t *pIndexes)
	Build the tree. More...

size_t	findNearest (size_t k, const GVec &vec, size_t nExclude)
	This is a helper method that finds the nearest neighbors. More...

size_t	findWithinRadius (double squaredRadius, const GVec &vec, size_t nExclude)
	This is a helper method that finds the neighbors within a specified radius. More...

Protected Member Functions inherited from GClasses::GNeighborFinderGeneralizing
void	insertionSortNeighbors (size_t start, size_t end)
	A helper method used by sortNeighbors when the remaining portion to sort is small. More...

Protected Attributes
size_t	m_maxLeafSize

GBallNode *	m_pRoot

size_t	m_size

Protected Attributes inherited from GClasses::GNeighborFinderGeneralizing
std::vector< double >	m_dists

std::vector< size_t >	m_neighs

bool	m_ownMetric

GDistanceMetric *	m_pMetric

Protected Attributes inherited from GClasses::GNeighborFinder
const GMatrix *	m_pData

Constructor & Destructor Documentation

GClasses::GBallTree::GBallTree	(	const GMatrix *	pData,
		GDistanceMetric *	pMetric = `NULL`,
		bool	ownMetric = `false`
	)

virtual GClasses::GBallTree::~GBallTree ( )

virtual

Member Function Documentation

GBallNode* GClasses::GBallTree::buildTree	(	size_t	count,
		size_t *	pIndexes
	)

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.)

virtual size_t GClasses::GBallTree::findNearest	(	size_t	k,
		size_t	index
	)

virtual

See the comment for GNeighborFinder::findNearest.

Implements GClasses::GNeighborFinder.

virtual size_t GClasses::GBallTree::findNearest	(	size_t	k,
		const GVec &	vec
	)

virtual

See the comment for GNeighborFinderGeneralizing::neighbors.

Implements GClasses::GNeighborFinderGeneralizing.

size_t GClasses::GBallTree::findNearest	(	size_t	k,
		const GVec &	vec,
		size_t	nExclude
	)

protected

This is a helper method that finds the nearest neighbors.

virtual size_t GClasses::GBallTree::findWithinRadius	(	double	squaredRadius,
		size_t	index
	)

virtual

See the comment for GNeighborFinder::findWithinRadius.

Implements GClasses::GNeighborFinder.

virtual size_t GClasses::GBallTree::findWithinRadius	(	double	squaredRadius,
		const GVec &	vec
	)

virtual

See the comment for GNeighborFinderGeneralizing::findWithinRadius.

Implements GClasses::GNeighborFinderGeneralizing.

size_t GClasses::GBallTree::findWithinRadius	(	double	squaredRadius,
		const GVec &	vec,
		size_t	nExclude
	)

protected

This is a helper method that finds the neighbors within a specified radius.

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 void GClasses::GBallTree::reoptimize ( )

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.

void GClasses::GBallTree::setMaxLeafSize ( size_t n )

inline

Specify the max number of point-vectors to store in each leaf node.

static void GClasses::GBallTree::test ( )

static

Performs unit tests for this class. Throws an exception if there is a failure.

Member Data Documentation

size_t GClasses::GBallTree::m_maxLeafSize

protected

GBallNode* GClasses::GBallTree::m_pRoot

protected

size_t GClasses::GBallTree::m_size

protected

Detailed Description

Public Member Functions

Static Public Member Functions

Protected Member Functions

Protected Attributes

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation