mlpack

RStarTree

The RStarTree class implements the R*-tree, a multidimensional space partitioning tree that can insert and remove points dynamically. The R*-tree is an improvement over the RTree: its growth procedure is more complex and thus slightly more expensive, but results in trees where internal nodes have less overlap, which means better performance for search and lookup tasks.

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

The R*-tree is generally less efficient for machine learning tasks than other trees such as the KDTree or Octree, but those trees do not support dynamic insertion or deletion of points. If insert/delete functionality is required, then the R-*-tree or other variants of RectangleTree should be chosen instead.

🔗 See also

🔗 Template parameters

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

RStarTree<DistanceType, StatisticType, MatType>

The RStarTree class itself is a convenience typedef of the generic RectangleTree class, using the RStarTreeSplit class as the split strategy, the RStarTreeDescentHeuristic class as the descent strategy, and NoAuxiliaryInformation as the auxiliary information type.

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

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

🔗 Constructors

RStarTrees are constructed by inserting points in a dataset sequentially. The dataset is not permuted during the construction process.

Notes:

🔗 Constructor parameters:

name type description default
data MatType 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
minLeafSize size_t Minimum number of points to store in each leaf. 8
maxNumChildren size_t Maximum number of children allowed in each non-leaf node. 5
minNumChildren size_t Minimum number of children in each non-leaf node. 2
dimensionality size_t Dimensionality of points to be held in the tree. (N/A)
       
x arma::vec Column vector: point to insert into tree. Should have type matching the column vector type associated with MatType, and must have node.Dataset().n_rows elements. (N/A)
i size_t Index of point in node.Dataset() to delete from node. (N/A)

🔗 Basic tree properties

Once an RStarTree 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 RStarTree, and so accessing them does not require any computation. In the documentation below, ElemType is the element type of the given MatType; e.g., if MatType is arma::mat, then ElemType is double.

Note: for more details on each bound quantity, see the developer documentation on bound quantities for trees.

🔗 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 RStarTree 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 an RStarTree 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 rectangle tree with a leaf size of 10.  (This means that leaf nodes
// cannot contain more than 10 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::RStarTree tree(...)` will work fine in C++20 or newer).
mlpack::RStarTree<> 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 children in the root, and the allowable range.
std::cout << "Number of children of root: " << tree.NumChildren()
    << "; allowable range: [" << tree.MinNumChildren() << ", "
    << tree.MaxNumChildren() << "]." << 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;
for (size_t i = 0; i < tree.NumChildren(); ++i)
{
  std::cout << "Descendant points of child " << i << ":  "
      << tree.Child(i).NumDescendants() << "." << std::endl;
}
std::cout << std::endl;

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

Build two RStarTrees 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 trees on the first half and the second half of points.
mlpack::RStarTree<> tree1(dataset.cols(0, dataset.n_cols / 2));
mlpack::RStarTree<> 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::RStarTree<>& node1 = tree1.Child(0).Child(0);

  // Get the leftmost grandchild of the second tree's root---if it exists.
  if (!tree2.IsLeaf() && !tree2.Child(0).IsLeaf())
  {
    mlpack::RStarTree<>& 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 << " 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 << " is furthest from node2."
        << std::endl;
  }
}

Build an RStarTree 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 RStarTree 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::RStarTree<mlpack::EuclideanDistance,
                  mlpack::EmptyStatistic,
                  arma::fmat> tree(std::move(dataset), 100);

// Save the tree 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 RStarTree from disk, then traverse it manually and find the number of leaf nodes with less 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::RStarTree<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 less 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;

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

// 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 an RStarTree by iteratively inserting points from the corel dataset, print some information, and then remove a few randomly chosen points.

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

// Create an empty tree of the right dimensionality.
mlpack::RStarTree<> t(dataset.n_rows);

// Insert points one by one for the first half of the dataset.
for (size_t i = 0; i < dataset.n_cols / 2; ++i)
  t.Insert(dataset.col(i));

std::cout << "After inserting half the points, the root node has "
    << t.NumDescendants() << " descendant points and "
    << t.NumChildren() << " child nodes." << std::endl;

// For the second half, insert the points backwards.
for (size_t i = dataset.n_cols - 1; i >= dataset.n_cols / 2; --i)
  t.Insert(dataset.col(i));

std::cout << "After inserting all the points, the root node has "
    << t.NumDescendants() << " descendant points and "
    << t.NumChildren() << " child nodes." << std::endl;

// Remove three random points.
t.Delete(mlpack::math::RandInt(0, t.NumDescendants()));
std::cout << "After removing 1 point, the root node has " << t.NumDescendants()
    << " descendant points." << std::endl;
t.Delete(mlpack::math::RandInt(0, t.NumDescendants()));
std::cout << "After removing 2 points, the root node has " << t.NumDescendants()
    << " descendant points." << std::endl;
t.Delete(mlpack::math::RandInt(0, t.NumDescendants()));
std::cout << "After removing 3 points, the root node has " << t.NumDescendants()
    << " descendant points." << std::endl;