谈晓军, 涂建光. 一种自适应的两阶段R树批生成算法[J]. 武汉大学学报 ( 信息科学版), 2003, 28(1): 31-38.
引用本文: 谈晓军, 涂建光. 一种自适应的两阶段R树批生成算法[J]. 武汉大学学报 ( 信息科学版), 2003, 28(1): 31-38.
TAN Xiaojun, TU Jianguang. An Adaptive Two-Phase Algorithm for Bulk Loading R-trees[J]. Geomatics and Information Science of Wuhan University, 2003, 28(1): 31-38.
Citation: TAN Xiaojun, TU Jianguang. An Adaptive Two-Phase Algorithm for Bulk Loading R-trees[J]. Geomatics and Information Science of Wuhan University, 2003, 28(1): 31-38.

一种自适应的两阶段R树批生成算法

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

  • 摘要: 介绍了一种新的R树批生成算法ATBL。本算法结合了自底向上的生成方式和以缓冲区树为基础的自顶向下方式的优点,通过对算法性能进行理论分析以及与其他多个算法进行比较研究,证明该算法在执行速度和所生成R树的查询性能方面都能达到令人满意的效果。

     

    Abstract: 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.

     

/

返回文章
返回