mlpack

CoverTree

The CoverTree class implements the cover tree, a hierarchical tree structure with favorable theoretical properties. The cover tree is useful for efficient distance operations (such as nearest neighbor search) in low to moderate dimensions.

mlpack’s CoverTree implementation supports three template parameters for configurable behavior, and implements all the functionality required by the TreeType API, plus some additional functionality specific to cover trees.

Due to the extra bookkeeping and complexity required to achieve its theoretical guarantees, the CoverTree is often not as fast for nearest neighbor search as the KDTree. However, CoverTree is more flexible: it is able to work with any distance metric, not just LMetric.

🔗 See also

🔗 Template parameters

The CoverTree class takes four template parameters, the first three of which are required by the TreeType API (see also this more detailed section).

CoverTree<DistanceType, StatisticType, MatType, RootPointPolicy>

If no template parameters are explicitly specified, then defaults are used:

CoverTree<> = CoverTree<EuclideanDistance, EmptyStatistic, arma::mat,
                        FirstPointIsRoot>

🔗 Constructors

CoverTrees are constructed level-by-level, without modifying the input dataset.

Notes:

🔗 Constructor parameters:

name type description default
data arma::mat Column-major matrix to build the tree on. Optionally pass with std::move(data) to transfer ownership to the tree. (N/A)
distance DistanceType Instantiated distance metric (optional). EuclideanDistance()
base double Shrinkage factor of each level of the cover tree. Must be greater than 1. 2.0

Notes:

🔗 Basic tree properties

Once a CoverTree object is constructed, various properties of the tree can be accessed or inspected. Many of these functions are required by the TreeType API.

🔗 Accessing members of a tree

See also the developer documentation for basic tree functionality in mlpack.

🔗 Accessing data held in a tree

🔗 Accessing computed bound quantities of a tree

The following quantities are cached for each node in a CoverTree, and so accessing them does not require any computation.

Notes:

🔗 Other functionality

🔗 Bounding distances with the tree

The primary use of trees in mlpack is bounding distances to points or other tree nodes. The following functions can be used for these tasks.

🔗 Tree traversals

Like every mlpack tree, the CoverTree class provides a single-tree and dual-tree traversal that can be paired with a RuleType class to implement a single-tree or dual-tree algorithm.

🔗 Example usage

Build a CoverTree on the cloud dataset and print basic statistics about the tree.

// See https://datasets.mlpack.org/cloud.csv.
arma::mat dataset;
mlpack::data::Load("cloud.csv", dataset, true);

// Build the cover tree with default options.
//
// The std::move() means that `dataset` will be empty after this call, and the
// tree will "own" the dataset.  No data will be copied during tree building,
// regardless of whether we used `std::move()`.
//
// Note that the '<>' isn't necessary if C++20 is being used (e.g.
// `mlpack::CoverTree tree(...)` will work fine in C++20 or newer).
mlpack::CoverTree<> tree(std::move(dataset));

// Print the point held by the root node and the radius of the ball that
// contains all points:
std::cout << "Root node:" << std::endl;
std::cout << " - Base: " << tree.Base() << "." << std::endl;
std::cout << " - Scale: " << tree.Scale() << "." << std::endl;
std::cout << " - Point: " << tree.Dataset().col(tree.Point()).t();
std::cout << std::endl;

// Print the number of descendant points of the root, and of each of its
// children.
std::cout << "Descendant points of root:        "
    << tree.NumDescendants() << "." << std::endl;
std::cout << "Number of children of root: " << tree.NumChildren() << "."
    << std::endl;
for (size_t c = 0; c < tree.NumChildren(); ++c)
{
  std::cout << " - Descendant points of child " << c << ": "
      << tree.Child(c).NumDescendants() << "." << std::endl;
}

Build two CoverTrees on subsets of the corel dataset and compute minimum and maximum distances between different nodes in the tree.

// See https://datasets.mlpack.org/corel-histogram.csv.
arma::mat dataset;
mlpack::data::Load("corel-histogram.csv", dataset, true);

// Build cover trees on the first half and the second half of points.
mlpack::CoverTree<> tree1(dataset.cols(0, dataset.n_cols / 2));
mlpack::CoverTree<> tree2(dataset.cols(dataset.n_cols / 2 + 1,
    dataset.n_cols - 1));

// Compute the maximum distance between the trees.
std::cout << "Maximum distance between tree root nodes: "
    << tree1.MaxDistance(tree2) << "." << std::endl;

// Get a grandchild of the first tree's root---if it exists.
if (!tree1.IsLeaf() && !tree1.Child(0).IsLeaf())
{
  mlpack::CoverTree<>& node1 = tree1.Child(0).Child(0);

  // Get a grandchild of the second tree's root---if it exists.
  if (!tree2.IsLeaf() && !tree2.Child(0).IsLeaf())
  {
    mlpack::CoverTree<>& node2 = tree2.Child(0).Child(0);

    // Print the minimum and maximum distance between the nodes.
    mlpack::Range dists = node1.RangeDistance(node2);
    std::cout << "Possible distances between two grandchild nodes: ["
        << dists.Lo() << ", " << dists.Hi() << "]." << std::endl;

    // Print the minimum distance between the first node and the first
    // descendant point of the second node.
    const size_t descendantIndex = node2.Descendant(0);
    const double descendantMinDist =
        node1.MinDistance(node2.Dataset().col(descendantIndex));
    std::cout << "Minimum distance between grandchild node and descendant "
        << "point: " << descendantMinDist << "." << std::endl;

    // Which child of node2 is closer to node1?
    const size_t closestIndex = node2.GetNearestChild(node1);
    std::cout << "Child " << closestIndex << " of node2 is closest to node1."
        << std::endl;

    // And which child of node1 is further from node2?
    const size_t furthestIndex = node1.GetFurthestChild(node2);
    std::cout << "Child " << furthestIndex << " of node1 is furthest from "
        << "node2." << std::endl;
  }
}

Build a CoverTree on 32-bit floating point data and save it to disk.

// See https://datasets.mlpack.org/corel-histogram.csv.
arma::fmat dataset;
mlpack::data::Load("corel-histogram.csv", dataset);

// Build the CoverTree using 32-bit floating point data as the matrix type.
// We will still use the default EmptyStatistic and EuclideanDistance
// parameters.
mlpack::CoverTree<mlpack::EuclideanDistance,
                  mlpack::EmptyStatistic,
                  arma::fmat> tree(dataset);

// Save the CoverTree to disk with the name 'tree'.
mlpack::data::Save("tree.bin", "tree", tree);

std::cout << "Saved tree with " << tree.Dataset().n_cols << " points to "
    << "'tree.bin'." << std::endl;

Load a 32-bit floating point CoverTree from disk, then traverse it manually and find the number of leaf nodes with fewer than 10 points.

// This assumes the tree has already been saved to 'tree.bin' (as in the example
// above).

// This convenient typedef saves us a long type name!
using TreeType = mlpack::CoverTree<mlpack::EuclideanDistance,
                                   mlpack::EmptyStatistic,
                                   arma::fmat>;

TreeType tree;
mlpack::data::Load("tree.bin", "tree", tree);
std::cout << "Tree loaded with " << tree.NumDescendants() << " points."
    << std::endl;

// Recurse in a depth-first manner.  Count both the total number of leaves, and
// the number of nodes with more than 100 descendants.
size_t moreThan100Count = 0;
size_t totalLeafCount = 0;
std::stack<TreeType*> stack;
stack.push(&tree);
while (!stack.empty())
{
  TreeType* node = stack.top();
  stack.pop();

  if (node->NumDescendants() > 100)
    ++moreThan100Count;

  if (node->IsLeaf())
    ++totalLeafCount;

  for (size_t c = 0; c < node->NumChildren(); ++c)
    stack.push(&node->Child(c));
}

// Note that it would be possible to use TreeType::SingleTreeTraverser to
// perform the recursion above, but that is more well-suited for more complex
// tasks that require pruning and other non-trivial behavior; so using a simple
// stack is the better option here.

// Print the results.
std::cout << "Tree contains " << totalLeafCount << " leaves." << std::endl;
std::cout << moreThan100Count << " nodes have more than 100 descendants."
    << std::endl;