%0 Journal Article %J Information Processing Letters %D 2007 %T Execution time analysis of a top-down R-tree construction algorithm %A Alborzi,Houman %A Samet, Hanan %K Bulk loading %K Data structures %K Packing %K R-trees %K Spatial databases %X 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. %B Information Processing Letters %V 101 %P 6 - 12 %8 2007/01/16/ %@ 0020-0190 %G eng %U http://www.sciencedirect.com/science/article/pii/S002001900600233X %N 1 %R 10.1016/j.ipl.2006.07.010