动态k值聚类的R-树空间索引构建

摘要

空间信息技术的日益发展与位置服务需求的不断增长，使得空间数据的管理成为当前空间信息研究领域的热点。空间数据具有数据量庞大、结构复杂、数据之间具有位置关联性的特点，加之对位置服务质量和检索速度要求的提高，需要恰当地组织它们，以便高效地管理、存储和分析空间数据。
　　采用索引技术组织空间数据，可以在检索时快速定位到指定位置，提高检索速度。R-树空间索引是当前主流的空间索引技术，它结构简明、适用范围广、动态性高，在构建过程中通常有三种方式——OBO（One by one）方式、预处理方式和聚类方式。OBO方式插入代价大、节点间交叠程度高；预处理方式降低了节点间交叠程度和构建复杂度，但不是按照空间实际分布构建；聚类方式利用聚类算法划分空间数据，尽可能把相近的空间数据组织在同一子树下，从整体上提高了索引效率。但是，目前采用的R-树空间聚类技术使用指定 k值的聚类算法，初始聚类中心随机或指定选取。这样聚类的结果受初始k值影响，且易受离群空间数据的干扰。
　　针对这一问题，本文在比较当前主流空间索引技术优缺点的基础上，以静态空间数据为对象，结合空间数据的实际分布，提出动态确定 k值的空间聚类算法（DynamicK-value Spatial Clustering Algorithm，DKSC）。该算法通过聚类划分空间数据，把同一子空间的数据组织在同一子树下，从根节点到叶子节点逐层构建R-树，形成高效的R-树空间索引。在构建完成之后，利用一种辅助结构实现对空间数据的高效批量插入。分别用百度地图API生成的真实数据集和程序生成的模拟数据集进行实验，结果表明该算法优化了构建的R-树空间索引且具有更高效的检索效率，辅助结构能够提高批量插入后的索引性能。

目录

封面

声明

中文摘要

英文摘要

目录

术语表：

第一章 绪论

1.1 本文研究的背景与意义

1.2 相关研究状况

1.3 本文的主要研究内容

1.4 论文组织结构

1.5 本章小结

第二章 空间数据索引技术

2.1 空间数据

2.2 空间检索

2.3 空间索引

2.4 R-树空间索引

2.5 空间聚类

2.6 本章小结

第三章 DKSC算法

3.1 相关定义

3.2 离群数据问题

3.3 聚类数和初始聚类中心

3.4 算法描述

3.5 实验分析

3.6 本章小结

第四章 基于辅助结构的批量插入方法

4.1 插入方法类型

4.2 基于辅助结构的批量插入方法

4.3 实验分析

4.4 本章小结

第五章 总结与展望

5.1 总结

5.2 展望

参考文献

致谢

攻读硕士学位期间发表的论文