Covertree Class Reference

#include <Covertree.h>

Data Structures
class	CoverTreeNode

Public Member Functions
	Covertree (int maxDist, const std::vector< Observation > &points=std::vector< Observation >())
	~Covertree ()
void	insert (const Observation &newObservation)
bool	isValidTree () const
void	remove (const Observation &p)
std::vector< Observation >	kNearestNeighbors (const Observation &p, const unsigned int &k) const
int	get_numberofobs ()
CoverTreeNode *	getRoot () const
void	print () const

Data Fields
double	base

Private Types
typedef std::pair< double, CoverTreeNode * >	distNodePair

Private Member Functions
distNodePair	distance (const Observation &p, const std::vector< CoverTreeNode * > &Q)
bool	insert_rec (const Observation &p, const std::vector< distNodePair > &Qi, const int &level)
std::vector< CoverTreeNode * >	kNearestNodes (const Observation &o, const unsigned int &k) const
void	remove_rec (const Observation &p, std::map< int, std::vector< distNodePair > > &coverSets, int level, bool &multi)

Private Attributes
CoverTreeNode *	_root
unsigned int	_numNodes
int	_maxLevel
int	_minLevel

Detailed Description

Definition at line 8 of file Covertree.h.

Member Typedef Documentation

distNodePair

typedef std::pair<double, CoverTreeNode*> Covertree::distNodePair

private

Definition at line 45 of file Covertree.h.

Constructor & Destructor Documentation

Covertree()

Covertree::Covertree	(	int	maxDist,
		const std::vector< Observation > &	points = std::vector<Observation>()
	)

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 6 of file Covertree.cpp.

                                                                     {/*{{{*/
   this->base = 2.;
   _root=NULL;
   _numNodes=0;
   _maxLevel=maxLevel;//ceilf(log(maxDist)/log(base));
   _minLevel=_maxLevel-1;
   std::vector<Observation>::const_iterator it;
   for(it=points.begin(); it!=points.end(); ++it) {
      this->insert(*it);//adds data to the covertree object
   }
}/*}}}*/

~Covertree()

Covertree::~Covertree

(

)

Definition at line 17 of file Covertree.cpp.

                     {/*{{{*/
   if(_root==NULL) return;
   //Get all of the root's children (from any level),
   //delete the root, repeat for each of the children
   std::vector<CoverTreeNode*> nodes;
   nodes.push_back(_root);
   while(!nodes.empty()) {
      CoverTreeNode* byeNode = nodes[0];
      nodes.erase(nodes.begin());
      std::vector<CoverTreeNode*> children = byeNode->getAllChildren();
      nodes.insert(nodes.begin(),children.begin(),children.end());
      delete byeNode;
   }   
}/*}}}*/

Member Function Documentation

distance()

std::pair< double, Covertree::CoverTreeNode * > Covertree::distance ( const Observation &  p, const std::vector< CoverTreeNode * > &  Q  )

private

Definition at line 33 of file Covertree.cpp.

                                                                                                                        {/*{{{*/
   double minDist = 1.e+50;
   CoverTreeNode* minNode;
   std::vector<CoverTreeNode*>::const_iterator it;
   for(it=Q.begin();it!=Q.end();++it) {
      double dist = p.distance((*it)->getObservation());
      if(dist < minDist) {
         minDist = dist;
         minNode = *it;
      }
   }
   return std::make_pair(minDist,minNode);  
}/*}}}*/

insert_rec()

bool Covertree::insert_rec ( const Observation &  p, const std::vector< distNodePair > &  Qi, const int &  level  )

private

Recursive implementation of the insert algorithm (see paper).

Definition at line 69 of file Covertree.cpp.

                                                                                                       {/*{{{*/
   std::vector<std::pair<double, CoverTreeNode*> > Qj;
   double sep = pow(base,level);
   double minDist = 1.e+50;
   std::pair<double,CoverTreeNode*> minQiDist(1.e+50,NULL);
   std::vector<std::pair<double, CoverTreeNode*> >::const_iterator it;
   for(it=Qi.begin(); it!=Qi.end(); ++it) {
      if(it->first<minQiDist.first) minQiDist = *it;
      if(it->first<minDist) minDist=it->first;
      if(it->first<=sep) Qj.push_back(*it);
      std::vector<CoverTreeNode*> children = it->second->getChildren(level);
      std::vector<CoverTreeNode*>::const_iterator it2;
      for(it2=children.begin();it2!=children.end();++it2) {
         double d = p.distance((*it2)->getObservation());
         if(d<minDist) minDist = d;
         if(d<=sep) {
            Qj.push_back(std::make_pair(d,*it2));
         }
      }
   }
   //std::cout << "level: " << level << ", sep: " << sep << ", dist: " << minQDist.first << "\n";
   if(minDist > sep) {
      return true;
   } else {
      bool found = insert_rec(p,Qj,level-1);
      //distNodePair minQiDist = distance(p,Qi);
      if(found && minQiDist.first <= sep) {
         if(level-1<_minLevel) _minLevel=level-1;
         minQiDist.second->addChild(level,
                  new CoverTreeNode(p));
         //std::cout << "parent is ";
         //minQiDist.second->getObservation().print();
         _numNodes++;
         return false;
      } else {
         return found;
      }
   }
}/*}}}*/

kNearestNodes()

std::vector< Covertree::CoverTreeNode * > Covertree::kNearestNodes ( const Observation &  o, const unsigned int &  k  ) const

private

Definition at line 108 of file Covertree.cpp.

                                                                                                            {/*{{{*/
   if(_root==NULL) return std::vector<CoverTreeNode*>();
   //maxDist is the kth nearest known point to p, and also the farthest
   //point from p in the set minNodes defined below.
   double maxDist = p.distance(_root->getObservation());
   //minNodes stores the k nearest known points to p.
   std::set<distNodePair> minNodes;
 
   minNodes.insert(std::make_pair(maxDist,_root));
   std::vector<distNodePair> Qj(1,std::make_pair(maxDist,_root));
   for(int level = _maxLevel; level>=_minLevel;level--) {
      std::vector<distNodePair>::const_iterator it;
      int size = Qj.size();
      for(int i=0; i<size; i++) {
         std::vector<CoverTreeNode*> children =
           Qj[i].second->getChildren(level);
         std::vector<CoverTreeNode*>::const_iterator it2;
         for(it2=children.begin(); it2!=children.end(); ++it2) {
            double d = p.distance((*it2)->getObservation());
            if(d < maxDist || minNodes.size() < k) {
               minNodes.insert(std::make_pair(d,*it2));
               //--minNodes.end() gives us an iterator to the greatest
               //element of minNodes.
               if(minNodes.size() > k) minNodes.erase(--minNodes.end());
               maxDist = (--minNodes.end())->first;
            }
            Qj.push_back(std::make_pair(d,*it2));
         }
      }
      double sep = maxDist + pow(base, level);
      size = Qj.size();
      for(int i=0; i<size; i++) {
         if(Qj[i].first > sep) {
            //quickly removes an element from a vector w/o preserving order.
            Qj[i]=Qj.back();
            Qj.pop_back();
            size--; i--;
         }
      }
   }
   std::vector<CoverTreeNode*> kNN;
   std::set<distNodePair>::const_iterator it;
   for(it=minNodes.begin();it!=minNodes.end();++it) {
      kNN.push_back(it->second);
   }
   return kNN;
}/*}}}*/

remove_rec()

void Covertree::remove_rec ( const Observation &  p, std::map< int, std::vector< distNodePair > > &  coverSets, int  level, bool &  multi  )

private

Definition at line 232 of file Covertree.cpp.

                                                                                                                         {/*{{{*/
   std::vector<distNodePair>& Qi = coverSets[level];
   std::vector<distNodePair>& Qj = coverSets[level-1];
   double minDist = 1.e+50;
   CoverTreeNode* minNode = _root;
   CoverTreeNode* parent = 0;
   double sep = pow(base, level);
   std::vector<distNodePair>::const_iterator it;
   //set Qj to be all children q of Qi such that p.distance(q)<=sep
   //and also keep track of the minimum distance from p to a node in Qj
   //note that every node has itself as a child, but the
   //getChildren function only returns non-self-children.
   for(it=Qi.begin();it!=Qi.end();++it) {
      std::vector<CoverTreeNode*> children = it->second->getChildren(level);
      double dist = it->first;
      if(dist<minDist) {
         minDist = dist;
         minNode = it->second;
      }
      if(dist <= sep) {
         Qj.push_back(*it);
      }
      std::vector<CoverTreeNode*>::const_iterator it2;
      for(it2=children.begin();it2!=children.end();++it2) {
         dist = p.distance((*it2)->getObservation());
         if(dist<minDist) {
            minDist = dist;
            minNode = *it2;
            if(dist == 0.0) parent = it->second;
         }
         if(dist <= sep) {
            Qj.push_back(std::make_pair(dist,*it2));
         }
      }
   }
   if(level>_minLevel) remove_rec(p,coverSets,level-1,multi);
   if(minNode->hasObservation(p)) {
      //the multi flag indicates the point we removed is from a
      //node containing multiple points, and we have removed it,
      //so we don't need to do anything else.
      if(multi) return;
      if(!minNode->isSingle()) {
         minNode->removeObservation(p);
         multi=true;
         return;
      }
      if(parent!=NULL) parent->removeChild(level, minNode);
      std::vector<CoverTreeNode*> children = minNode->getChildren(level-1);
      std::vector<distNodePair>& Q = coverSets[level-1];
      if(Q.size()==1 && Q[0].second==minNode) {
         Q.pop_back();
      } else {
         for(unsigned int i=0;i<Q.size();i++) {
            if(Q[i].second==minNode) {
               Q[i]=Q.back();
               Q.pop_back();
               break;
            }
         }
      }
      std::vector<CoverTreeNode*>::const_iterator it;
      for(it=children.begin();it!=children.end();++it) {
         int i = level-1;
         Observation q = (*it)->getObservation();
         double minDQ = 1.e+50;
         CoverTreeNode* minDQNode = NULL;
         double sep = pow(base,i);
         bool br=false;
         while(true) {
            std::vector<distNodePair>&
              Q = coverSets[i];
            std::vector<distNodePair>::const_iterator it2;
            minDQ = 1.e+50;
            for(it2=Q.begin();it2!=Q.end();++it2) {
               double d = q.distance(it2->second->getObservation());
               if(d<minDQ) {
                  minDQ = d;
                  minDQNode = it2->second;
                  if(d <=sep) {
                     br=true;
                     break;
                  }
               }
            }
            minDQ=1.e+50;
            if(br) break;
            Q.push_back(std::make_pair((*it)->distance(p),*it));
            i++;
            sep = pow(base,i);
         }
         //minDQNode->getObservation().print();
         //std::cout << " is level " << i << " parent of ";
         //(*it)->getObservation().print();
         if (minDQNode != NULL)
          minDQNode->addChild(i,*it);
      }
      if(parent!=NULL) {
         delete minNode;
         _numNodes--;
      }
   }
}/*}}}*/

insert()

void Covertree::insert

(

const Observation &

newObservation

)

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 49 of file Covertree.cpp.

                                                         {/*{{{*/
   if(_root==NULL) {
      _root = new CoverTreeNode(newObservation);
      _numNodes=1;
      return;
   }
   //TODO: this is pretty inefficient, there may be a better way
   //to check if the node already exists...
   CoverTreeNode* n = kNearestNodes(newObservation,1)[0];
   if(newObservation.distance(n->getObservation())==0.0) {
      n->addObservation(newObservation);
   } else {
      //insert_rec acts under the assumption that there are no nodes with
      //distance 0 to newObservation in the cover tree (the previous lines check it)
      insert_rec(newObservation,
               std::vector<distNodePair>
               (1,std::make_pair(_root->distance(newObservation),_root)),
               _maxLevel);
   }
}/*}}}*/

isValidTree()

bool Covertree::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 376 of file Covertree.cpp.

                                    {/*{{{*/
   if(_numNodes==0)
    return _root==NULL;
 
   std::vector<CoverTreeNode*> nodes;
   nodes.push_back(_root);
   for(int i=_maxLevel;i>_minLevel;i--) {
      double sep = pow(base,i);
      std::vector<CoverTreeNode*>::const_iterator it, it2;
      //verify separation invariant of cover tree: for each level,
      //every point is farther than base^level away
      for(it=nodes.begin(); it!=nodes.end(); ++it) {
         for(it2=nodes.begin(); it2!=nodes.end(); ++it2) {
            double dist=(*it)->distance((*it2)->getObservation());
            if(dist<=sep && dist!=0.0) {
               std::cout << "Level " << i << " Separation invariant failed.\n";
               return false;
            }
         }
      }
      std::vector<CoverTreeNode*> allChildren;
      for(it=nodes.begin(); it!=nodes.end(); ++it) {        
         std::vector<CoverTreeNode*> children = (*it)->getChildren(i);
         //verify covering tree invariant: the children of node n at level
         //i are no further than base^i away
         for(it2=children.begin(); it2!=children.end(); ++it2) {
            double dist = (*it2)->distance((*it)->getObservation());
            if(dist>sep) {
               std::cout << "Level" << i << " covering tree invariant failed.n";
               return false;
            }
         }
         allChildren.insert
           (allChildren.end(),children.begin(),children.end());
      }
      nodes.insert(nodes.begin(),allChildren.begin(),allChildren.end());
   }
   return true;
}/*}}}*/

remove()

void Covertree::remove

(

const Observation &

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 194 of file Covertree.cpp.

                                            {/*{{{*/
   //Most of this function's code is for the special case of removing the root
   if(_root==NULL) return;
   bool removingRoot=_root->hasObservation(p);
   if(removingRoot && !_root->isSingle()) {
      _root->removeObservation(p);
      return;
   }
   CoverTreeNode* newRoot=NULL;
   if(removingRoot) {
      if(_numNodes==1) {
         //removing the last node...
         delete _root;
         _numNodes--;
         _root=NULL;
         return;
      } else {
         for(int i=_maxLevel;i>_minLevel;i--) {
            if(!(_root->getChildren(i).empty())) {
               newRoot = _root->getChildren(i).back();
               _root->removeChild(i,newRoot);
               break;
            }
         }
      }
   }
   std::map<int, std::vector<distNodePair> > coverSets;
   coverSets[_maxLevel].push_back(std::make_pair(_root->distance(p),_root));
   if(removingRoot)
    coverSets[_maxLevel].push_back(std::make_pair(newRoot->distance(p),newRoot));
   bool multi = false;
   remove_rec(p,coverSets,_maxLevel,multi);
   if(removingRoot) {
      delete _root;
      _numNodes--;
      _root=newRoot;
   }
}/*}}}*/

kNearestNeighbors()

std::vector< Observation > Covertree::kNearestNeighbors	(	const Observation &	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 155 of file Covertree.cpp.

                                                                                                    {/*{{{*/
   if(_root==NULL) return std::vector<Observation>();
   std::vector<CoverTreeNode*> v = kNearestNodes(p, k);
   std::vector<Observation> kNN;
   std::vector<CoverTreeNode*>::const_iterator it;
   for(it=v.begin();it!=v.end();++it) {
      const std::vector<Observation>& p = (*it)->getObservations();
      kNN.insert(kNN.end(),p.begin(),p.end());
      if(kNN.size() >= k) break;
   }
   return kNN;
}/*}}}*/

get_numberofobs()

int Covertree::get_numberofobs

(

)

Definition at line 46 of file Covertree.cpp.

                              {/*{{{*/
   return _numNodes;
}/*}}}*/

getRoot()

Covertree::CoverTreeNode * Covertree::getRoot

(

)

const

Definition at line 367 of file Covertree.cpp.

                                                {/*{{{*/
   return _root;
}/*}}}*/

print()

void Covertree::print

(

)

const

Print the cover tree.

Definition at line 167 of file Covertree.cpp.

                             {/*{{{*/
   int d = _maxLevel-_minLevel+1;
   std::vector<CoverTreeNode*> Q;
   Q.push_back(_root);
   for(int i=0;i<d;i++) {
      std::cout << "LEVEL " << _maxLevel-i << "\n";
      std::vector<CoverTreeNode*>::const_iterator it;
      for(it=Q.begin();it!=Q.end();++it) {
         (*it)->getObservation().print();
         std::vector<CoverTreeNode*>
           children = (*it)->getChildren(_maxLevel-i);
         std::vector<CoverTreeNode*>::const_iterator it2;
         for(it2=children.begin();it2!=children.end();++it2) {
            std::cout << "  ";
            (*it2)->getObservation().print();
         }
      }
      std::vector<CoverTreeNode*> newQ;
      for(it=Q.begin();it!=Q.end();++it) {
         std::vector<CoverTreeNode*>
           children = (*it)->getChildren(_maxLevel-i);
         newQ.insert(newQ.end(),children.begin(),children.end());
      }
      Q.insert(Q.end(),newQ.begin(),newQ.end());
      std::cout << "\n\n";
   }
}/*}}}*/

Field Documentation

_root

CoverTreeNode* Covertree::_root

private

Definition at line 47 of file Covertree.h.

_numNodes

unsigned int Covertree::_numNodes

private

Definition at line 48 of file Covertree.h.

_maxLevel

int Covertree::_maxLevel

private

Definition at line 49 of file Covertree.h.

_minLevel

int Covertree::_minLevel

private

Definition at line 51 of file Covertree.h.

base

double Covertree::base

Definition at line 65 of file Covertree.h.

---

The documentation for this class was generated from the following files:

• src/c/classes/kriging/Covertree.h
• src/c/classes/kriging/Covertree.cpp