Execution time analysis of a top-down R-tree construction algorithm
A detailed CPU execution-time analysis and implementation are given for a bulk loading algorithm to construct R-trees due to Garcia et al. [Y.J. Garcia, M.A. Lopez, S.T. Leutenegger, A greedy algorithm for bulk loading R-trees, in: GIS'98: Proc. of the 6th ACM Intl. Syrup. 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. (c) 2006 Elsevier B.V. All rights reserved.
r-trees bulk loading packing spatial databases data structures