CoverTree Class Reference
A cover tree is a data structure forstering the fast computation of nearest neighbor queries. More...
#include <CoverTree.h>
Classes | |
| struct | Node |
| struct | tNode |
Public Member Functions | |
| CoverTree (const Array< double > &points) | |
| Construct a cover tree for the given set of points. | |
| virtual | ~CoverTree () |
| Destructor. | |
| unsigned int | OneNN (const Array< double > &query) const |
| This method computes the nearest neighbor of an arbitrary query point (one that was not used to construct the tree). | |
| unsigned int | SecondNN (unsigned int query) const |
| This method computes the nearest neighbor of a point that was used to construct the tree, but not the point itself. | |
| void | KNN (const Array< double > &query, unsigned int k, std::vector< unsigned int > &neighbors) const |
| This method computes the k nearest neighbors of an arbitrary query point (one that was not used to construct the tree). | |
| const ArrayReference< double > | Point (unsigned int index) const |
| This method returns the point corresponding to an index as returned by the different query methods. | |
| virtual double | distance2 (const Array< double > &p1, const Array< double > &p2) const |
| compute the squared distance | |
| double | distance (const Array< double > &p1, const Array< double > &p2) const |
Protected Member Functions | |
| Node * | freeNode () |
| void | Insert (unsigned int index) |
Protected Attributes | |
| const Array< double > * | points |
| Node * | root |
| std::vector< Node > | mem |
| unsigned int | usedmem |
Friends | |
| bool | cmp (const tNode &n1, const tNode &n2) |
Detailed Description
A cover tree is a data structure forstering the fast computation of nearest neighbor queries.The algorithm is described in:
Alina Beygelzimer, Sham M. Kakade, and John Langford. Cover Trees for Nearest Neighbor. ICML 2006. Cover tree data structure for fast nearest neighbors
- A cover tree is a data structure for fast processing of nearest neighbor queries. The algorithm is described in:
- Alina Beygelzimer, Sham M. Kakade, and John Langford. Cover Trees for Nearest Neighbor. ICML 2006.
Definition at line 32 of file CoverTree.h.
Constructor & Destructor Documentation
| CoverTree::CoverTree | ( | const Array< double > & | points | ) |
Construct a cover tree for the given set of points.
Definition at line 36 of file CoverTree.cpp.
References CoverTree::Node::firstchild, freeNode(), i, CoverTree::Node::index, Insert(), mem, CoverTree::Node::nextsibling, POINTSCALE, root, CoverTree::Node::scale, and usedmem.
| CoverTree::~CoverTree | ( | ) | [virtual] |
Member Function Documentation
| double CoverTree::distance | ( | const Array< double > & | p1, | |
| const Array< double > & | p2 | |||
| ) | const [inline] |
Definition at line 76 of file CoverTree.h.
References distance2().
Referenced by KNN(), OneNN(), and SecondNN().
| double CoverTree::distance2 | ( | const Array< double > & | p1, | |
| const Array< double > & | p2 | |||
| ) | const [virtual] |
compute the squared distance
- This method computes the squared distance between p1 and p2. Override this method to change the distance computation.
Reimplemented in KernelCoverTree.
Definition at line 292 of file CoverTree.cpp.
Referenced by distance(), Insert(), and SecondNN().
| Node* CoverTree::freeNode | ( | ) | [inline, protected] |
| void CoverTree::Insert | ( | unsigned int | index | ) | [protected] |
Definition at line 300 of file CoverTree.cpp.
References distance2(), CoverTree::Node::firstchild, freeNode(), i_log2(), CoverTree::Node::index, CoverTree::Node::nextsibling, points, POINTSCALE, root, and CoverTree::Node::scale.
Referenced by CoverTree().
| void CoverTree::KNN | ( | const Array< double > & | query, | |
| unsigned int | k, | |||
| std::vector< unsigned int > & | neighbors | |||
| ) | const |
This method computes the k nearest neighbors of an arbitrary query point (one that was not used to construct the tree).
Returns the induces of the nearest neighbors.
- Parameters:
-
query query point k number of neighbors neighbors list of neighbor indices
Definition at line 223 of file CoverTree.cpp.
References cmp, CoverTree::tNode::dist, distance(), CoverTree::Node::firstchild, i, i_pow2(), CoverTree::Node::index, CoverTree::Node::nextsibling, CoverTree::tNode::node, points, root, and CoverTree::Node::scale.
| unsigned int CoverTree::OneNN | ( | const Array< double > & | query | ) | const |
This method computes the nearest neighbor of an arbitrary query point (one that was not used to construct the tree).
Returns the index of the nearest neighbor.
Definition at line 60 of file CoverTree.cpp.
References CoverTree::tNode::dist, distance(), CoverTree::Node::firstchild, i, i_pow2(), CoverTree::Node::index, CoverTree::Node::nextsibling, CoverTree::tNode::node, points, root, and CoverTree::Node::scale.
| const ArrayReference<double> CoverTree::Point | ( | unsigned int | index | ) | const [inline] |
This method returns the point corresponding to an index as returned by the different query methods.
Definition at line 63 of file CoverTree.h.
| unsigned int CoverTree::SecondNN | ( | unsigned int | query | ) | const |
This method computes the nearest neighbor of a point that was used to construct the tree, but not the point itself.
Returns the index of the nearest neighbor.
Definition at line 124 of file CoverTree.cpp.
References CoverTree::tNode::dist, distance(), distance2(), CoverTree::Node::firstchild, i, i_pow2(), CoverTree::Node::index, CoverTree::Node::nextsibling, CoverTree::tNode::node, points, root, and CoverTree::Node::scale.
Friends And Related Function Documentation
Member Data Documentation
std::vector<Node> CoverTree::mem [protected] |
const Array<double>* CoverTree::points [protected] |
Node* CoverTree::root [protected] |
Definition at line 106 of file CoverTree.h.
Referenced by CoverTree(), Insert(), KNN(), OneNN(), and SecondNN().
unsigned int CoverTree::usedmem [protected] |
The documentation for this class was generated from the following files: