An efficient algorithm for finding neighbors. More...

#include <GNeighborFinder.h>

Inheritance diagram for GClasses::GKdTree:

Public Member Functions
	GKdTree (const GMatrix pData, size_t neighborCount, GDistanceMetric pMetric=NULL, bool ownMetric=false)

virtual	~GKdTree ()

GKdNode *	buildTree (size_t count, size_t *pIndexes)
	Build the tree. More...

bool	isGreaterOrEqual (const double *pPat, size_t attr, double pivot)
	Returns true iff the specified point-vector is on the >= side of the specified pivot. 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...

GKdNode *	root ()
	Returns the root node of the kd-tree. 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 double	medianDistanceToNeighbor (GMatrix &data, size_t n)
	Computes the median distance to the n^th closest neighbor of each row in data. More...

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
void	computePivotAndGoodness (size_t count, size_t pIndexes, size_t attr, double pOutPivot, double *pOutGoodness)
	Computes a good pivot for the specified attribute, and the goodness of splitting on that attribute. For continuous attributes, the pivot is the (not scaled) mean and the goodness is the scaled variance. For nominal attributes, the pivot is the most common value and the goodness is scaled entropy. More...

void	findNeighbors (size_t pOutNeighbors, double pOutDistances, const double *pInputVector, size_t nExclude)
	This is the helper method that finds the neighbors. More...

size_t	splitIndexes (size_t count, size_t *pIndexes, size_t attr, double pivot)
	Moves all the indexes that refer to rows that have a value less than pivot in the specified attribute to the beginning of the list, and the rest to the end. Returns the number of rows with a value less than the pivot. For nominal values, not-equal values are moved to the beginning, and equal values are moved to the end. More...

Protected Attributes
size_t	m_maxLeafSize

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

Constructor & Destructor Documentation

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

virtual GClasses::GKdTree::~GKdTree ( )

virtual

Member Function Documentation

GKdNode* GClasses::GKdTree::buildTree	(	size_t	count,
		size_t *	pIndexes
	)

Build the tree.

void GClasses::GKdTree::computePivotAndGoodness	(	size_t	count,
		size_t *	pIndexes,
		size_t	attr,
		double *	pOutPivot,
		double *	pOutGoodness
	)

protected

Computes a good pivot for the specified attribute, and the goodness of splitting on that attribute. For continuous attributes, the pivot is the (not scaled) mean and the goodness is the scaled variance. For nominal attributes, the pivot is the most common value and the goodness is scaled entropy.

void GClasses::GKdTree::findNeighbors	(	size_t *	pOutNeighbors,
		double *	pOutDistances,
		const double *	pInputVector,
		size_t	nExclude
	)

protected

This is the helper method that finds the neighbors.

bool GClasses::GKdTree::isGreaterOrEqual	(	const double *	pPat,
		size_t	attr,
		double	pivot
	)

Returns true iff the specified point-vector is on the >= side of the specified pivot.

static double GClasses::GKdTree::medianDistanceToNeighbor	(	GMatrix &	data,
		size_t	n
	)

static

Computes the median distance to the n^th closest neighbor of each row in data.

virtual void GClasses::GKdTree::neighbors	(	size_t *	pOutNeighbors,
		size_t	index
	)

virtual

See the comment for GNeighborFinder::neighbors.

Implements GClasses::GNeighborFinder.

virtual void GClasses::GKdTree::neighbors	(	size_t *	pOutNeighbors,
		double *	pOutDistances,
		size_t	index
	)

virtual

See the comment for GNeighborFinder::neighbors.

Implements GClasses::GNeighborFinder.

virtual void GClasses::GKdTree::neighbors	(	size_t *	pOutNeighbors,
		double *	pOutDistances,
		const double *	pInputVector
	)

virtual

See the comment for GNeighborFinderGeneralizing::neighbors.

Implements GClasses::GNeighborFinderGeneralizing.

virtual void GClasses::GKdTree::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.

GKdNode* GClasses::GKdTree::root ( )

inline

Returns the root node of the kd-tree.

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

inline

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

size_t GClasses::GKdTree::splitIndexes	(	size_t	count,
		size_t *	pIndexes,
		size_t	attr,
		double	pivot
	)

protected

Moves all the indexes that refer to rows that have a value less than pivot in the specified attribute to the beginning of the list, and the rest to the end. Returns the number of rows with a value less than the pivot. For nominal values, not-equal values are moved to the beginning, and equal values are moved to the end.

static void GClasses::GKdTree::test ( )

static

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

Member Data Documentation

size_t GClasses::GKdTree::m_maxLeafSize

protected

GKdNode* GClasses::GKdTree::m_pRoot

protected

size_t GClasses::GKdTree::m_size

protected

Public Member Functions

Static Public Member Functions

Protected Member Functions

Protected Attributes

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation