tpl_r_star_tree.H File Reference

R*-tree: an R-tree tuned with the Beckmann-Kriegel-Schneider-Seeger heuristics. More...

#include <tpl_r_tree.H>

Include dependency graph for tpl_r_star_tree.H:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Namespaces
namespace	Aleph
	Main namespace for Aleph-w library functions.

Typedefs
template<typename Payload , size_t MaxEntries = 16, size_t MinEntries = MaxEntries / 2>
using	Aleph::RStarTree = RTree< Payload, MaxEntries, MinEntries, RTreeVariant::RStar >
	Dynamic R*-tree spatial index (R-tree with the R*-tree heuristics).

Detailed Description

R*-tree: an R-tree tuned with the Beckmann-Kriegel-Schneider-Seeger heuristics.

RStarTree<Payload, MaxEntries, MinEntries> is the same dynamic spatial index as RTree (same API, same Rectangle/Payload entries, same exact rational coordinates), but built with the R*-tree insertion strategy instead of Guttman's quadratic split. It is a thin alias over RTree<Payload, MaxEntries, MinEntries, RTreeVariant::RStar>, so it shares all of RTree's query, deletion, verification and copy/move machinery.

Relative to the plain R-tree, the R*-tree changes three things:

• ChooseSubtree: when descending into a node whose children are leaves, it picks the child whose growth adds the least overlap with its siblings (ties broken by least area enlargement, then least area), instead of only minimizing area enlargement.
• Node split: it chooses the split axis that minimizes the summed perimeter (margin) of the two resulting groups, then the distribution along that axis that minimizes their overlap area (ties: minimum total area), instead of Guttman's quadratic seed/assignment split.
• Forced reinsertion: the first time a leaf overflows during an insertion, rather than splitting immediately it removes the entries farthest from the leaf centre and reinserts them from the root. This tends to produce more compact, less overlapping trees and better query performance. Reinsertion here is applied at the leaf level (internal overflows split with the R*-tree heuristic).

These heuristics usually yield lower node overlap and faster queries than the plain R-tree at the cost of somewhat more work per insertion. All structural invariants, complexity classes, exception-safety, thread-safety and reference-invalidation rules are exactly those documented for RTree in tpl_r_tree.H.

Definition in file tpl_r_star_tree.H.