| 刘焱,方金云,韩承德.一种基于形状分析的R树节点分裂算法[J].高技术通讯(中文),2010,20(1):55~60 |
| 一种基于形状分析的R树节点分裂算法 |
| An R tree node splitting algorithm based on shape analysis |
| |
| DOI： |
| 中文关键词: 地理信息系统(GIS)， 空间数据库， 空间索引， R树， 节点分裂算法 |
| 英文关键词: geographical information systems (GIS), spatial database, spatial index, R tree, node splitting algorithm |
| 基金项目:863计划(2009AA12Z226)资助项目 |
| 作者 | 单位 | | 刘焱 | 中国科学院计算技术研究所集成应用中心地理信息事业部；中国科学院研究生院 | | 方金云 | 中国科学院计算技术研究所集成应用中心地理信息事业部 | | 韩承德 | 中国科学院计算技术研究所集成应用中心地理信息事业部 |
|
| 摘要点击次数: 2912 |
| 全文下载次数: 2245 |
| 中文摘要: |
| 基于对最小边界矩形(MBR)形状的分析，提出了一种线性时间复杂度的R树空间索引节点分裂算法。该算法将节点及其记录的最小边界矩形按形状分类，并根据分类情况确定节点分裂策略。首先提出了一种基于形状分析的基本节点分裂算法，然后针对其可能产生的不平衡分裂结果，提出了一种分裂结果平衡算法。最后提出了一种考虑兄弟节点的联合分裂策略以进一步提升算法的效果。对比实验表明，无论在索引的创建过程还是查询过程，此算法效率都优于对比算法，并且具有易实现和适应性强等特点，可以应用于各种空间数据库和地理信息系统(GIS)。 |
| 英文摘要: |
| The paper proposes an R tree node splitting algorithm based on the analysis of shapes of minimum bounding rectangles (MBRs). The algorithm classifies MBRs of nodes and records, and decides the splitting policy based on their shapes. At first a shape based basic partition algorithm is described. Then to deal with possible uneven splitting results, a balancing algorithm is proposed. At last a joint splitting algorithm is developed using siblings to improve the splitting results. The comparison experiments showed that the proposed algorithm outperformed the comparison algorithms in both the creation process and the query process. Besides, the algorithm is easy to implement and adaptable to various types of data. It can be used in many kinds of spatial database systems and geographical information systems (GIS). |
|
查看全文
查看/发表评论 下载PDF阅读器 |
| 关闭 |
