The STRtree: Sort-Tile-Recursive Spatial Indexing

When the full set of rectangles to be indexed is known in advance, we can build an R-tree far more efficiently than by inserting one rectangle at a time. The Sort-Tile-Recursive (STR) algorithm bulk-loads the data into a tightly packed, nearly-balanced tree by sorting on one axis at a time and slicing the sorted list into uniform groups.

For a 2D dataset of $N$ rectangles with node capacity $M$, STR begins by computing three sizing parameters:

• Number of leaf nodes: $L = \lceil N/M \rceil.$
• Number of vertical slices: $S = \lceil \sqrt{L}\, \rceil.$
• Rectangles per slice: $S \cdot M.$

Each slice will eventually be split into $S$ leaves of $M$ rectangles, so the leaf level holds at most $S^2$ leaves and $S^2 M$ rectangles. The last slice (and the last leaf within it) may be partially filled when $N < S^2 M.$

For example, with $N = 18$ and $M = 2{:}$

$$L = \lceil 18/2 \rceil = 9, \qquad S = \lceil \sqrt{9}\, \rceil = 3, \qquad S \cdot M = 6.$$

We partition the 18 rectangles into 3 vertical slices of 6 rectangles each, and within each slice we form 3 leaves of 2 rectangles.