12#ifndef MLPACK_CORE_TREE_COVER_TREE_COVER_TREE_HPP
13#define MLPACK_CORE_TREE_COVER_TREE_COVER_TREE_HPP
18#include "../statistic.hpp"
95template<
typename MetricType = metric::LMetric<2, true>,
96 typename StatisticType = EmptyStatistic,
97 typename MatType = arma::mat,
98 typename RootPo
intPolicy = FirstPo
intIsRoot>
120 MetricType* metric = NULL);
191 const size_t pointIndex,
195 arma::Col<size_t>& indices,
196 arma::vec& distances,
200 MetricType& metric = NULL);
220 const size_t pointIndex,
224 const ElemType furthestDescendantDistance,
225 MetricType* metric = NULL);
260 template<
typename Archive>
272 template<
typename RuleType>
276 template<
typename RuleType>
279 template<
typename RuleType>
283 const MatType&
Dataset()
const {
return *dataset; }
286 size_t Point()
const {
return point; }
288 size_t Point(
const size_t)
const {
return point; }
290 bool IsLeaf()
const {
return (children.size() == 0); }
304 const std::vector<CoverTree*>&
Children()
const {
return children; }
306 std::vector<CoverTree*>&
Children() {
return children; }
325 const StatisticType&
Stat()
const {
return stat; }
327 StatisticType&
Stat() {
return stat; }
333 template<
typename VecType>
335 const VecType& point,
342 template<
typename VecType>
344 const VecType& point,
418 {
return furthestDescendantDistance; }
430 center = arma::vec(dataset->col(point));
434 MetricType&
Metric()
const {
return *metric; }
438 const MatType* dataset;
442 std::vector<CoverTree*> children;
450 size_t numDescendants;
456 ElemType furthestDescendantDistance;
467 void CreateChildren(arma::Col<size_t>& indices,
468 arma::vec& distances,
471 size_t& usedSetSize);
484 void ComputeDistances(
const size_t pointIndex,
485 const arma::Col<size_t>& indices,
486 arma::vec& distances,
487 const size_t pointSetSize);
502 size_t SplitNearFar(arma::Col<size_t>& indices,
503 arma::vec& distances,
505 const size_t pointSetSize);
526 size_t SortPointSet(arma::Col<size_t>& indices,
527 arma::vec& distances,
528 const size_t childFarSetSize,
529 const size_t childUsedSetSize,
530 const size_t farSetSize);
532 void MoveToUsedSet(arma::Col<size_t>& indices,
533 arma::vec& distances,
537 arma::Col<size_t>& childIndices,
538 const size_t childFarSetSize,
539 const size_t childUsedSetSize);
540 size_t PruneFarSet(arma::Col<size_t>& indices,
541 arma::vec& distances,
543 const size_t nearSetSize,
544 const size_t pointSetSize);
550 void RemoveNewImplicitNodes();
562 friend class boost::serialization::access;
568 template<
typename Archive>
575 size_t distanceComps;
582#include "cover_tree_impl.hpp"
585#include "../cover_tree.hpp"
Simple real-valued range.
A dual-tree cover tree traverser; see dual_tree_traverser.hpp.
A single-tree cover tree traverser; see single_tree_traverser.hpp for implementation.
A cover tree is a tree specifically designed to speed up nearest-neighbor computation in high-dimensi...
size_t GetFurthestChild(const VecType &point, typename std::enable_if_t< IsVector< VecType >::value > *=0)
Return the index of the furthest child node to the given query point.
ElemType MaxDistance(const CoverTree &other) const
Return the maximum distance to another node.
ElemType MaxDistance(const arma::vec &other, const ElemType distance) const
Return the maximum distance to another point given that the distance from the center to the point has...
CoverTree(const MatType &dataset, MetricType &metric, const ElemType base=2.0)
Create the cover tree with the given dataset and the given instantiated metric.
ElemType MinDistance(const arma::vec &other, const ElemType distance) const
Return the minimum distance to another point given that the distance from the center to the point has...
math::RangeType< ElemType > RangeDistance(const CoverTree &other, const ElemType distance) const
Return the minimum and maximum distance to another node given that the point-to-point distance has al...
size_t GetNearestChild(const VecType &point, typename std::enable_if_t< IsVector< VecType >::value > *=0)
Return the index of the nearest child node to the given query point.
size_t NumChildren() const
Get the number of children.
ElemType MinimumBoundDistance() const
Get the minimum distance from the center to any bound edge (this is the same as furthestDescendantDis...
MatType::elem_type ElemType
The type held by the matrix type.
CoverTree(const MatType &dataset, const ElemType base, const size_t pointIndex, const int scale, CoverTree *parent, const ElemType parentDistance, arma::Col< size_t > &indices, arma::vec &distances, size_t nearSetSize, size_t &farSetSize, size_t &usedSetSize, MetricType &metric=NULL)
Construct a child cover tree node.
ElemType & ParentDistance()
Modify the distance to the parent.
size_t NumDescendants() const
Get the number of descendant points.
CoverTree *& Parent()
Modify the parent node.
ElemType & Base()
Modify the base; don't do this, you'll break everything.
CoverTree(const CoverTree &other)
Create a cover tree from another tree.
StatisticType & Stat()
Modify the statistic for this node.
CoverTree(const MatType &dataset, const ElemType base=2.0, MetricType *metric=NULL)
Create the cover tree with the given dataset and given base.
CoverTree(Archive &ar, const typename std::enable_if_t< Archive::is_loading::value > *=0)
Create a cover tree from a boost::serialization archive.
size_t Point() const
Get the index of the point which this node represents.
CoverTree & operator=(const CoverTree &other)
Copy the given Cover Tree.
ElemType Base() const
Get the base.
ElemType MinDistance(const CoverTree &other, const ElemType distance) const
Return the minimum distance to another node given that the point-to-point distance has already been c...
MatType Mat
So that other classes can access the matrix type.
math::RangeType< ElemType > RangeDistance(const CoverTree &other) const
Return the minimum and maximum distance to another node.
CoverTree(const MatType &dataset, const ElemType base, const size_t pointIndex, const int scale, CoverTree *parent, const ElemType parentDistance, const ElemType furthestDescendantDistance, MetricType *metric=NULL)
Manually construct a cover tree node; no tree assembly is done in this constructor,...
CoverTree()
A default constructor.
math::RangeType< ElemType > RangeDistance(const arma::vec &other) const
Return the minimum and maximum distance to another point.
CoverTree & operator=(CoverTree &&other)
Take ownership of the given Cover Tree.
int & Scale()
Modify the scale of this node. Be careful...
size_t DistanceComps() const
const std::vector< CoverTree * > & Children() const
Get the children.
ElemType MaxDistance(const arma::vec &other) const
Return the maximum distance to another point.
int Scale() const
Get the scale of this node.
math::RangeType< ElemType > RangeDistance(const arma::vec &other, const ElemType distance) const
Return the minimum and maximum distance to another point given that the point-to-point distance has a...
ElemType MaxDistance(const CoverTree &other, const ElemType distance) const
Return the maximum distance to another node given that the point-to-point distance has already been c...
const CoverTree & Child(const size_t index) const
Get a particular child node.
ElemType MinDistance(const arma::vec &other) const
Return the minimum distance to another point.
ElemType & FurthestDescendantDistance()
Modify the distance from the center of the node to the furthest descendant.
ElemType MinDistance(const CoverTree &other) const
Return the minimum distance to another node.
size_t Descendant(const size_t index) const
Get the index of a particular descendant point.
void Center(arma::vec ¢er) const
Get the center of the node and store it in the given vector.
CoverTree(MatType &&dataset, MetricType &metric, const ElemType base=2.0)
Create the cover tree with the given dataset and the given instantiated metric, taking ownership of t...
const StatisticType & Stat() const
Get the statistic for this node.
CoverTree(MatType &&dataset, const ElemType base=2.0)
Create the cover tree with the given dataset, taking ownership of the dataset.
size_t GetNearestChild(const CoverTree &queryNode)
Return the index of the nearest child node to the given query node.
CoverTree & Child(const size_t index)
Modify a particular child node.
CoverTree(CoverTree &&other)
Move constructor for a Cover Tree, possess all the members of the given tree.
size_t GetFurthestChild(const CoverTree &queryNode)
Return the index of the furthest child node to the given query node.
MetricType & Metric() const
Get the instantiated metric.
ElemType FurthestPointDistance() const
Get the distance to the furthest point. This is always 0 for cover trees.
CoverTree *& ChildPtr(const size_t index)
const MatType & Dataset() const
Get a reference to the dataset.
ElemType FurthestDescendantDistance() const
Get the distance from the center of the node to the furthest descendant.
~CoverTree()
Delete this cover tree node and its children.
CoverTree * Parent() const
Get the parent node.
size_t Point(const size_t) const
For compatibility with other trees; the argument is ignored.
void serialize(Archive &ar, const unsigned int)
Serialize the tree.
ElemType ParentDistance() const
Get the distance to the parent.
std::vector< CoverTree * > & Children()
Modify the children manually (maybe not a great idea).
Linear algebra utility functions, generally performed on matrices or vectors.
typename enable_if< B, T >::type enable_if_t
The core includes that mlpack expects; standard C++ includes and Armadillo.
Definition of the Range class, which represents a simple range with a lower and upper bound.
If value == true, then VecType is some sort of Armadillo vector or subview.