Editing R-tree (section)

=== Bulk-loading ===

* Nearest-X: Objects are sorted by their first coordinate ("X") and then split into pages of the desired size.
* Packed [[Hilbert R-tree]]: variation of Nearest-X, but sorting using the Hilbert value of the center of a rectangle instead of using the X coordinate. There is no guarantee the pages will not overlap.
* Sort-Tile-Recursive (STR):<ref>{{cite web | first1 = Scott T. | last1 = Leutenegger | first2 = Jeffrey M. | last2 = Edgington | first3 = Mario A. | last3 = Lopez | url = https://archive.org/details/nasa_techdoc_19970016975 | title = STR: A Simple and Efficient Algorithm for R-Tree Packing |date=February 1997}}</ref> Another variation of Nearest-X, that estimates the total number of leaves required as <math>l=\lceil \text{number of objects} / \text{capacity}\rceil</math>, the required split factor in each dimension to achieve this as <math>s=\lceil l^{1/d}\rceil</math>, then repeatedly splits each dimensions successively into <math>s</math> equal sized partitions using 1-dimensional sorting. The resulting pages, if they occupy more than one page, are again bulk-loaded using the same algorithm. For point data, the leaf nodes will not overlap, and "tile" the data space into approximately equal sized pages.
* Overlap Minimizing Top-down (OMT):<ref>{{cite web | first1 = Taewon | last1 = Lee | first2 = Sukho | last2 = Lee | url = http://ftp.informatik.rwth-aachen.de/Publications/CEUR-WS/Vol-74/files/FORUM_18.pdf | title =  OMT: Overlap Minimizing Top-down Bulk Loading Algorithm for R-tree | date=June 2003}}</ref> Improvement over STR using a top-down approach which minimizes overlaps between slices and improves query performance.
* [[Priority R-tree]]

{{Expand section|date=June 2008}}