A Novel Implementation of Dynamic R-tree Based on Lazy Splitting and Clustering

R*树是目前公认查询效果很好的R树变体,但是其构造代价较原始R树增加数倍,对于插入删除和更新频繁的空间数据效果不好.为此,本文提出一种基于惰性聚类分裂技术的R树动态实现方法(LR树).惰性聚类分裂技术是在对象插入节点导致溢出时不立即进行分裂,而是尝试将其插入到邻近的未满节点中,直到邻近节点均已满时,再利用聚类技术进行节点分裂,在邻近节点和分裂节点之间重组入口项.LR树在确保查询性能的前提下,大大降低了构造代价,并且大幅提高了索引结构的空间利用率.最后的分析和实验证明了LR树的高效性.国家自然科学基金中文核心期刊要目总览(PKU)中国科技核心期刊(ISTIC)中国科学引文数据库(CSCD)04102-103,1253