mlpack::tree::RStarTreeSplit Class Reference

A Rectangle Tree has new points inserted at the bottom. More...

#include <r_star_tree_split.hpp>

Static Public Member Functions
template<typename TreeType >
static void	SplitLeafNode (TreeType *tree, std::vector< bool > &relevels)
	Split a leaf node using the algorithm described in "The R*-tree: An Efficient and Robust Access method for Points and Rectangles. More...
template<typename TreeType >
static bool	SplitNonLeafNode (TreeType *tree, std::vector< bool > &relevels)
	Split a non-leaf node using the "default" algorithm. More...
template<typename TreeType >
static size_t	ReinsertPoints (TreeType *tree, std::vector< bool > &relevels)
	Reinsert any points into the tree, if needed. More...
template<typename TreeType >
static void	PickLeafSplit (TreeType *tree, size_t &bestAxis, size_t &bestIndex)
	Given a node, return the best dimension and the best index to split on. More...

Detailed Description

A Rectangle Tree has new points inserted at the bottom.

When these nodes overflow, we split them, moving up the tree and splitting nodes as necessary.

Member Function Documentation

PickLeafSplit()

template<typename TreeType >

void mlpack::tree::RStarTreeSplit::PickLeafSplit ( TreeType *  tree, size_t &  bestAxis, size_t &  bestIndex  )

static

Given a node, return the best dimension and the best index to split on.

Check each dimension, to find which dimension is best to split on.

ReinsertPoints()

template<typename TreeType >

size_t mlpack::tree::RStarTreeSplit::ReinsertPoints ( TreeType *  tree, std::vector< bool > &  relevels  )

static

Reinsert any points into the tree, if needed.

This returns the number of points reinserted.

SplitLeafNode()

template<typename TreeType >

void mlpack::tree::RStarTreeSplit::SplitLeafNode ( TreeType *  tree, std::vector< bool > &  relevels  )

static

Split a leaf node using the algorithm described in "The R*-tree: An Efficient and Robust Access method for Points and Rectangles.

We call GetPointSeeds to get the two points which will be the initial points in the new nodes We then call AssignPointDestNode to assign the remaining points to the two new nodes.

" If necessary, this split will propagate upwards through the tree.

Finally, we delete the old node and insert the new nodes into the tree, spliting the parent if necessary.

Now that we have found the best dimension to split on, re-sort in that dimension to prepare for reinsertion of points into the new nodes.

If 'tree' is the root of the tree (i.e. if it has no parent), then we must create two new child nodes, distribute the points from the original node among them, and insert those. If 'tree' is not the root of the tree, then we may create only one new child node, redistribute the points from the original node between 'tree' and the new node, then insert those nodes into the parent.

Here we simply set treeOne and treeTwo to the right values to avoid code duplication.

SplitNonLeafNode()

template<typename TreeType >

bool mlpack::tree::RStarTreeSplit::SplitNonLeafNode ( TreeType *  tree, std::vector< bool > &  relevels  )

static

Split a non-leaf node using the "default" algorithm.

We call GetBoundSeeds to get the two new nodes that this one will be broken into.

If this is a root node, the tree increases in depth.

Then we call AssignNodeDestNode to move the children of this node into either of those two nodes. Finally, we delete the now unused information and recurse up the tree if necessary. We don't need to worry about the bounds higher up the tree because they were already updated if necessary.

Check over each dimension to see which is best to use for splitting.

If 'tree' is the root of the tree (i.e. if it has no parent), then we must create two new child nodes, distribute the children from the original node among them, and insert those. If 'tree' is not the root of the tree, then we may create only one new child node, redistribute the children from the original node between 'tree' and the new node, then insert those nodes into the parent.

Here, we simply set treeOne and treeTwo to the right values to avoid code duplication.

---

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

• src/mlpack/core/tree/rectangle_tree/r_star_tree_split.hpp
• src/mlpack/core/tree/rectangle_tree/r_star_tree_split_impl.hpp