TY - JOUR
T1 - Execution time analysis of a top-down R-tree construction algorithm
JF - Information Processing Letters
Y1 - 2007
A1 - Alborzi,Houman
A1 - Samet, Hanan
KW - Bulk loading
KW - Data structures
KW - Packing
KW - R-trees
KW - Spatial databases
AB - A detailed CPU execution-time analysis and implementation are given for a bulk loading algorithm to construct R-trees due to García et al. [Y.J. García, M.A. López, S.T. Leutenegger, A greedy algorithm for bulk loading R-trees, in: GIS'98: Proc. of the 6th ACM Intl. Symp. on Advances in Geographic Information Systems, Washington, DC, 1998, pp. 163–164] which is known as the top-down greedy split (TGS) bulk loading algorithm. The TGS algorithm makes use of a classical bottom-up packing approach. In addition, an alternative packing approach termed top-down packing is introduced which may lead to improved query performance, and it is shown how to incorporate it into the TGS algorithm. A discussion is also presented of the tradeoffs of using the bottom-up and top-down packing approaches.
VL - 101
SN - 0020-0190
UR - http://www.sciencedirect.com/science/article/pii/S002001900600233X
CP - 1
M3 - 10.1016/j.ipl.2006.07.010
ER -