An Adaptive Two-Phase Algorithm for Bulk Loading R-trees

This paper presents a new algorithm called ATBL for performing bulk loading on R-trees.When constructing a spatial index,there are two important factors:the speed of construction algorithm and the performance of the spatial index structure.The traditional repeated insertion algorithm can not meet the need of increased data volume,and most bulk loading algorithms can not pay attention to both factors.After the comprehensive study of present bulk loading algorithms,the authors divide numerous algorithms into two categories:bottom-up and top-down,and put forward ATBL algorithms.ATBL,which is based on buffer tree technology,utilizes the forced reinsert policy of R^*-tree and combines the advantage of the two kinds of bulk loading algorithms.We give a theoretical analysis of our algorithm and make comparison study with previous algorithms using an extensive set of experiments.The result shows that it is efficient in terms of I/O complexity and can produce a good quality index in terms of query performance.