mlpack

MeanSplitKDTree

The MeanSplitKDTree class represents a k-dimensional binary space partitioning tree, and is a well-known data structure for efficient distance operations (such as nearest neighbor search) in low dimensions—typically less than 100. This is very similar to the KDTree class, except that a different splitting strategy is used to split nodes in the tree.

In general, a MeanSplitKDTree will be a better balanced tree and have fewer nodes than a KDTree. However, counterintuitively, a more balanced tree can be worse for search tasks like nearest neighbor search, because unbalanced nodes are more easily pruned away during search. In general, using a KDTree for nearest neighbor search is 20-80% faster, but this is not true for every dataset or task.

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

🔗 See also

🔗 Template parameters

In accordance with the TreeType API (see also this more detailed section), the MeanSplitKDTree class takes three template parameters:

MeanSplitKDTree<DistanceType, StatisticType, MatType>

The MeanSplitKDTree class itself is a convenience typedef of the generic BinarySpaceTree class, using the HRectBound class as the bounding structure, and using the MeanSplit splitting strategy for construction, which splits a node in the dimension of maximum variance on the midpoint of the bound’s range in that dimension.

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

MeanSplitKDTree<> = MeanSplitKDTree<EuclideanDistance, EmptyStatistic, arma::mat>

🔗 Constructors

MeanSplitKDTrees are efficiently constructed by permuting points in a dataset in a quicksort-like algorithm. However, this means that the ordering of points in the tree’s dataset (accessed with node.Dataset()) after construction may be different.

Notes:

🔗 Constructor parameters:

name type description default
data arma::mat Column-major matrix to build the tree on. Pass with std::move(data) to avoid copying the matrix. (N/A)
maxLeafSize size_t Maximum number of points to store in each leaf. 20
oldFromNew std::vector<size_t> Mappings from points in node.Dataset() to points in data. (N/A)
newFromOld std::vector<size_t> Mappings from points in data to points in node.Dataset(). (N/A)

🔗 Basic tree properties

Once a MeanSplitKDTree 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 MeanSplitKDTree, 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 MeanSplitKDTree 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.

In addition to those two classes, which are required by the TreeType policy, an additional traverser is available:

🔗 Example usage

Build a MeanSplitKDTree 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 kd-tree with a leaf size of 10.  (This means that nodes are split
// until they contain 10 or fewer points.)
//
// The std::move() means that `dataset` will be empty after this call, and no
// data will be copied during tree building.
//
// Note that the '<>' isn't necessary if C++20 is being used (e.g.
// `mlpack::MeanSplitKDTree tree(...)` will work fine in C++20 or newer).
mlpack::MeanSplitKDTree<> tree(std::move(dataset));

// Print the bounding box of the root node.
std::cout << "Bounding box of root node:" << std::endl;
for (size_t i = 0; i < tree.Bound().Dim(); ++i)
{
  std::cout << " - Dimension " << i << ": [" << tree.Bound()[i].Lo() << ", "
      << tree.Bound()[i].Hi() << "]." << std::endl;
}
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 << "Descendant points of left child:  "
    << tree.Left()->NumDescendants() << "." << std::endl;
std::cout << "Descendant points of right child: "
    << tree.Right()->NumDescendants() << "." << std::endl;
std::cout << std::endl;

// Compute the center of the kd-tree.
arma::vec center;
tree.Center(center);
std::cout << "Center of kd-tree: " << center.t();

Build two MeanSplitKDTrees 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 mean-split kd-trees on the first half and the second half of points.
mlpack::MeanSplitKDTree<> tree1(dataset.cols(0, dataset.n_cols / 2));
mlpack::MeanSplitKDTree<> 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 the leftmost grandchild of the first tree's root---if it exists.
if (!tree1.IsLeaf() && !tree1.Child(0).IsLeaf())
{
  mlpack::MeanSplitKDTree<>& node1 = tree1.Child(0).Child(0);

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

    // 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 closerIndex = node2.GetNearestChild(node1);
    if (closerIndex == 0)
      std::cout << "The left child of node2 is closer to node1." << std::endl;
    else if (closerIndex == 1)
      std::cout << "The right child of node2 is closer to node1." << std::endl;
    else // closerIndex == 2 in this case.
      std::cout << "Both children of node2 are equally close to node1."
          << std::endl;

    // And which child of node1 is further from node2?
    const size_t furtherIndex = node1.GetFurthestChild(node2);
    if (furtherIndex == 0)
      std::cout << "The left child of node1 is further from node2."
          << std::endl;
    else if (furtherIndex == 1)
      std::cout << "The right child of node1 is further from node2."
          << std::endl;
    else // furtherIndex == 2 in this case.
      std::cout << "Both children of node1 are equally far from node2."
          << std::endl;
  }
}

Build a MeanSplitKDTree 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 MeanSplitKDTree using 32-bit floating point data as the matrix
// type.  We will still use the default EmptyStatistic and EuclideanDistance
// parameters.  A leaf size of 100 is used here.
mlpack::MeanSplitKDTree<mlpack::EuclideanDistance,
                        mlpack::EmptyStatistic,
                        arma::fmat> tree(std::move(dataset), 100);

// Save the MeanSplitKDTree 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 MeanSplitKDTree 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::MeanSplitKDTree<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 leaves with fewer than 10 points.
size_t leafCount = 0;
size_t totalLeafCount = 0;
std::stack<TreeType*> stack;
stack.push(&tree);
while (!stack.empty())
{
  TreeType* node = stack.top();
  stack.pop();

  if (node->NumPoints() < 10)
    ++leafCount;
  ++totalLeafCount;

  if (!node->IsLeaf())
  {
    stack.push(node->Left());
    stack.push(node->Right());
  }
}

// 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 << leafCount << " out of " << totalLeafCount << " leaves have fewer "
  << "than 10 points." << std::endl;

Build a MeanSplitKDTree and map between original points and new points.

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

// Build the tree.
std::vector<size_t> oldFromNew, newFromOld;
mlpack::MeanSplitKDTree<> tree(dataset, oldFromNew, newFromOld);

// oldFromNew and newFromOld will be set to the same size as the dataset.
std::cout << "Number of points in dataset: " << dataset.n_cols << "."
    << std::endl;
std::cout << "Size of oldFromNew: " << oldFromNew.size() << "." << std::endl;
std::cout << "Size of newFromOld: " << newFromOld.size() << "." << std::endl;
std::cout << std::endl;

// See where point 42 in the tree's dataset came from.
std::cout << "Point 42 in the permuted tree's dataset:" << std::endl;
std::cout << "  " << tree.Dataset().col(42).t();
std::cout << "Was originally point " << oldFromNew[42] << ":" << std::endl;
std::cout << "  " << dataset.col(oldFromNew[42]).t();
std::cout << std::endl;

// See where point 7 in the original dataset was mapped.
std::cout << "Point 7 in original dataset:" << std::endl;
std::cout << "  " << dataset.col(7).t();
std::cout << "Mapped to point " << newFromOld[7] << ":" << std::endl;
std::cout << "  " << tree.Dataset().col(newFromOld[7]).t();

Compare the MeanSplitKDTree to a KDTree on a dataset.

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

// Build the trees.
mlpack::KDTree<> kdtree(dataset);
mlpack::MeanSplitKDTree<> mskdtree(dataset);

// Compute the number of nodes and leaves in each tree, the average volume of
// leaf nodes, and the average volume of non-leaf nodes.
double leafVolume = 0.0;
double nonleafVolume = 0.0;
size_t numNodes = 0;
size_t numLeaves = 0;

// We will compute the quantities using a stack to do a depth-first traversal of
// the tree.
std::stack<mlpack::KDTree<>*> kdStack;
kdStack.push(&kdtree);
while (!kdStack.empty())
{
  mlpack::KDTree<>* node = kdStack.top();
  kdStack.pop();

  ++numNodes;
  if (node->IsLeaf())
  {
    ++numLeaves;
    leafVolume += node->Bound().Volume();
  }
  else
  {
    nonleafVolume += node->Bound().Volume();
    kdStack.push(node->Left());
    kdStack.push(node->Right());
  }
}

// Print statistics about the KDTree.
std::cout << "KDTree statistics:" << std::endl;
std::cout << " - Number of nodes: " << numNodes << "." << std::endl;
std::cout << " - Number of leaves: " << numLeaves << "." << std::endl;
std::cout << " - Average leaf volume: " << (leafVolume / numLeaves) << "."
    << std::endl;
std::cout << " - Average non-leaf volume: "
    << (nonleafVolume / (numNodes - numLeaves)) << "." << std::endl;

// Now compute the same quantities for the MeanSplitKDTree.
leafVolume = 0.0;
nonleafVolume = 0.0;
numLeaves = 0;
numNodes = 0;
std::stack<mlpack::MeanSplitKDTree<>*> mskdStack;
mskdStack.push(&mskdtree);
while (!mskdStack.empty())
{
  mlpack::MeanSplitKDTree<>* node = mskdStack.top();
  mskdStack.pop();

  ++numNodes;
  if (node->IsLeaf())
  {
    ++numLeaves;
    leafVolume += node->Bound().Volume();
  }
  else
  {
    nonleafVolume += node->Bound().Volume();
    mskdStack.push(node->Left());
    mskdStack.push(node->Right());
  }
}

// Print statistics about the MeanSplitKDTree.
std::cout << "MeanSplitKDTree statistics:" << std::endl;
std::cout << " - Number of nodes: " << numNodes << "." << std::endl;
std::cout << " - Number of leaves: " << numLeaves << "." << std::endl;
std::cout << " - Average leaf volume: " << (leafVolume / numLeaves) << "."
    << std::endl;
std::cout << " - Average non-leaf volume: "
    << (nonleafVolume / (numNodes - numLeaves)) << "." << std::endl;