%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