Classes | Public Member Functions | Static Public Attributes

CoverTree< Point > Class Template Reference

Detailed Description

template<class Point>
class shogun::CoverTree< Point >

Cover Tree. Allows for insertion, removal, and k-nearest-neighbor queries.

The user should define double Point::distance(const Point& p) and bool Point::operator==(const Point& p), where p1.distance(p2)==0 doesn't necessarily mean that p1==p2).

For example, a point could consist of a vector and a string name, where their distance measure is simply euclidean distance but to be equal they must have the same name in addition to having distance 0.

Definition at line 52 of file CoverTree.h.

List of all members.


class  CoverTreeNode

Public Member Functions

 CoverTree (const double &maxDist, const std::vector< Point > &points=std::vector< Point >())
 ~CoverTree ()
bool isValidTree () const
void insert (const Point &newPoint)
void remove (const Point &p)
std::vector< Point > kNearestNeighbors (const Point &p, const unsigned int &k) const
CoverTreeNode * getRoot () const

Static Public Attributes

static const double base = 2.0

Constructor & Destructor Documentation

CoverTree ( const double &  maxDist,
const std::vector< Point > &  points = std::vector<Point>() 

Constructs a cover tree which begins with all points in points.

maxDist should be the maximum distance that any two points can have between each other. IE p.distance(q) < maxDist for all p,q that you will ever try to insert. The cover tree may be invalid if an inaccurate maxDist is given.

Definition at line 185 of file CoverTree.h.

~CoverTree (  ) 

Definition at line 199 of file CoverTree.h.

Member Function Documentation

CoverTree< Point >::CoverTreeNode * getRoot (  )  const

get the root node of the tree

root node

Definition at line 517 of file CoverTree.h.

void insert ( const Point &  newPoint  ) 

Insert newPoint into the cover tree. If newPoint is already present, (that is, newPoint==p for some p already in the tree), then the tree is unchanged. If p.distance(newPoint)==0.0 but newPoint!=p, then newPoint WILL be inserted and both points may be returned in k-nearest- neighbor searches.

Definition at line 437 of file CoverTree.h.

bool isValidTree (  )  const

Just for testing/debugging. Returns true iff the cover tree satisfies the the covering tree invariants (every node in level i is greater than base^i distance from every other node, and every node in level i is less than or equal to base^i distance from its children). See the cover tree papers for details.

Definition at line 608 of file CoverTree.h.

std::vector< Point > kNearestNeighbors ( const Point &  p,
const unsigned int &  k 
) const

Returns the k nearest points to p in order (the 0th element of the vector is closest to p, 1th is next, etc). It may return greater than k points if there is a tie for the kth place.

Definition at line 501 of file CoverTree.h.

void remove ( const Point &  p  ) 

Remove point p from the cover tree. If p is not present in the tree, it will remain unchanged. Otherwise, this will remove exactly one point q from the tree satisfying p==q.

Definition at line 460 of file CoverTree.h.

Member Data Documentation

const double base = 2.0 [static]

base level of cover tree

Definition at line 126 of file CoverTree.h.

The documentation for this class was generated from the following file:
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines

SHOGUN Machine Learning Toolbox - Documentation