基于改进Chameleon算法的R树构建

作     者：贺乃洲 

作者单位：太原理工大学 

学位级别：硕士

导师姓名：安建成

授予年度：2020年

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 

主      题：空间索引 Chameleon算法 R树 K-MEDOIDS算法 布谷鸟算法 

摘      要：由于空间数据的维度属性和位置关系的可变性,空间数据库的主要工作是处理大量空间数据,并且它可以合理有效地完成所需的添加、删除、修改以及其他功能。对空间数据进行索引特别重要,索引不仅可以改变数据的存储结构,优化存储过程,还可以实现更快地执行类似查询的操作。大多数空间数据的索引结构为R树,而R树是在一维数据中广泛使用的B树索引结构在空间上的扩展。R树的传统构造是通过动态插入技术实现的,即逐步插入空间数据以形成R树。在这种情况下,不仅R树的构造结果有很大的机会陷入局部最优,而且频繁的节点分裂,会造成最小外包矩形的重叠面积大幅度增加,这将导致多路径查询问题,影响最终检索效率。针对以上问题,本文按照以下两个方面展开研究:一、结合DBSCAN（Density-Based Spatial Clustering of Applications with Noise）算法优势对Chameleon进行改进,改进算法不仅降低了K-最邻近图中先验参数的影响,也避免了hmetis算法划分不合理造成子簇局部最优的问题。然后基于改进的Chameleon算法,提出了一种批量生成索引的方式,这种方式综合考虑了数据对象间互连性和相似性的特征,使得节点内数据更加紧凑,减少了节点最小外包矩形的重叠面积,从而避免了查询中的多路径检索问题,提高了算法的检索效率。二、由于批生成索引方式的时间复杂度较高,于是提出结合实现简易的K-MEDOIDS算法,同时运用布谷鸟算法改进初始解任意的弊端,对改进算法结果进行再次聚类。这不仅减少了噪声点对R树构建的影响,还减少了索引的构建时间,提高了R树的构建质量。最后,在模拟数据集和真实分类数据上,通过对比不同算法构建R树的实验,结果表明该算法缩短了R树的构建时间,降低了最小外包矩形的重叠面积,具有高效的检索效率。