GClasses

GClasses::GKdTree Class Reference

An efficient algorithm for finding neighbors. More...

#include <GNeighborFinder.h>

Inheritance diagram for GClasses::GKdTree:
GClasses::GNeighborFinderGeneralizing GClasses::GNeighborFinder

List of all members.

Public Member Functions

 GKdTree (GMatrix *pData, size_t neighborCount, GDistanceMetric *pMetric, bool ownMetric)
virtual ~GKdTree ()
virtual size_t addCopy (const double *pVector)
 Add a new point-vector to the internal set.
virtual double * releaseVector (size_t nIndex)
 Release a point-vector from the internal set.
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.
virtual void neighbors (size_t *pOutNeighbors, size_t index)
 See the comment for GNeighborFinder::neighbors.
virtual void neighbors (size_t *pOutNeighbors, double *pOutDistances, size_t index)
 See the comment for GNeighborFinder::neighbors.
virtual void neighbors (size_t *pOutNeighbors, double *pOutDistances, const double *pInputVector)
 See the comment for GNeighborFinderGeneralizing::neighbors.
void setMaxLeafSize (size_t n)
 Specify the max number of point-vectors to store in each leaf node.
GKdNode * root ()
 Returns the root node of the kd-tree.
GKdNode * buildTree (size_t count, size_t *pIndexes)
 Build the tree.
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.

Static Public Member Functions

static void test ()
 Performs unit tests for this class. Throws an exception if there is a failure.
static double medianDistanceToNeighbor (GMatrix &data, size_t n)
 Computes the median distance to the n^th closest neighbor of each row in data.

Protected Member Functions

void findNeighbors (size_t *pOutNeighbors, double *pOutDistances, const double *pInputVector, size_t nExclude)
 This is the helper method that finds the neighbors.
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.
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.

Protected Attributes

size_t m_maxLeafSize
size_t m_size
GKdNode * m_pRoot

Detailed Description

An efficient algorithm for finding neighbors.


Constructor & Destructor Documentation

GClasses::GKdTree::GKdTree ( GMatrix pData,
size_t  neighborCount,
GDistanceMetric pMetric,
bool  ownMetric 
)
virtual GClasses::GKdTree::~GKdTree ( ) [virtual]

Member Function Documentation

virtual size_t GClasses::GKdTree::addCopy ( const double *  pVector) [virtual]

Add a new point-vector to the internal set.

Implements GClasses::GNeighborFinderGeneralizing.

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]
virtual double* GClasses::GKdTree::releaseVector ( size_t  nIndex) [virtual]

Release a point-vector from the internal set.

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

GKdNode* GClasses::GKdTree::m_pRoot [protected]
size_t GClasses::GKdTree::m_size [protected]