基于向量近似的复合空间索引研究

发布时间：2017-10-21 09:07

  本文关键词：基于向量近似的复合空间索引研究

  更多相关文章： 向量近似 复合空间索引 复合空间查询 非均匀划分

【摘要】：随着对地观测手段的不断发展,人类获取空间数据的能力达到空前的水平。快速准确地从海量空间数据中获取有效的信息,既是GIS可用性的前提,也是对空间数据进一步分析应用的基础。复合空间查询是一种常用的空间查询方式,通过几何与属性条件复合进行查询以获取用户需要的空间信息。为了提高复合空间查询的效率,一般通过空间索引和属性索引进行剪枝,但由于需要在不同字段上分别建立索引,一方面增加了索引维护的复杂性,降低了存储效率,另一方面割裂了特征间可能存在的相关性,降低了查询效率。本文提出一种复合空间索引,该索引引入向量近似思想并进行空间化扩展,利用特征间的相关性实现对几何与属性特征同时剪枝,借助二进制位向量和计算机高效的位运算能力,实现了较高的查询效率和较低的存储开销。尤其需要指出,该索引无需建立基于MBR的空间索引结构,通过隐式空间剪枝即可实现更精确的空间过滤。论文的主要研究内容和成果如下：(1)提出了向量近似空间化扩展方法。论文对比分析了均匀划分和非均匀划分对查询效率的影响,提出了在几何和属性特征上建立非均匀划分的优化划分方案,并采用向量近似思想将空间数据的多维特征映射到一维线性空间中。该扩展方法具有低存储和高性能等优点。(2)提出了一种基于向量近似的复合空间索引(VAHSI, Vector Approximation based Hybrid Spatial Index)。该索引基于空间化向量近似思想把空间数据集映射为一系列数据桶。在一级过滤层,基于计数排序思想,建立了空间数据集与数据桶的高速映射表,基于该高速映射表,无需任何辅助结构,可以实现在O(1)时间内对数据桶的直接定位；在二级索引层,根据数据桶的数据密度,分别采用位向量和枚举法建立桶索引。查询时首先对查询条件进行分解,通过高速映射表高速剪枝,然后利用桶索引和位运算进行二次快速剪枝以获得更精炼的候选数据集,最后对候选数据集进行精确过滤。论文给出了该复合空间索引的查询、插入和删除算法。(3)构建了基于VAHSI的复合空间查询原型系统,在此基础上进行了一系列对比实验,对实验结果的分析表明,本文提出的复合空间索引具有高性能和低存储开销的特性。
【关键词】：向量近似 复合空间索引 复合空间查询 非均匀划分
【学位授予单位】：南京师范大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：P208
【目录】：

• 摘要4-5
• Abstract5-12
• 第1章 绪论12-19
• 1.1 选题背景和研究意义12
• 1.2 研究现状及存在问题12-15
• 1.2.1 国内外研究现状12-15
• 1.2.2 存在的问题15
• 1.3 研究目标和研究内容15-16
• 1.4 技术路线16-18
• 1.5 本文的组织结构18-19
• 第2章 向量近似方法及其空间化扩展19-28
• 2.1 向量近似方法研究19-20
• 2.2 属性特征映射规则20-24
• 2.2.1 属性特征均匀映射20-21
• 2.2.2 属性特征非均匀映射21-24
• 2.3 几何特征映射规则24-26
• 2.3.1 几何特征均匀映射24-25
• 2.3.2 几何特征非均匀映射25-26
• 2.4 几何与属性特征复合映射规则26-27
• 2.5 本章小结27-28
• 第3章 基于向量近似的复合空间索引VAHSI28-43
• 3.1 VAHSI索引结构28-29
• 3.2 VAHSI构建方法29-35
• 3.3 VAHSI索引方法35-39
• 3.4 VAHSI维护方法39-42
• 3.5 本章小结42-43
• 第4章 基于VAHSI的复合空间查询实验与结果分析43-59
• 4.1 原型系统设计与实现43-45
• 4.1.1 核心类43
• 4.1.2 系统功能43-44
• 4.1.3 系统界面44-45
• 4.2 实验数据45-47
• 4.2.1 开发环境45
• 4.2.2 实验方案45-47
• 4.3 实验与结果分析47-58
• 4.4 本章小结58-59
• 第5章 结论与展望59-60
• 5.1 研究结论59
• 5.2 后续展望59-60
• 参考文献60-65
• 致谢65

【参考文献】

中国期刊全文数据库 前4条

1 董道国;刘振中;薛向阳;;VA-Trie:一种用于近似k近邻查询的高维索引结构[J];计算机研究与发展;2005年12期

2 刘云生,王洪庭,廖国琼;利用HB+树的复合索引问题的解决方案[J];计算机工程;2005年17期

3 徐少平;王命延;王炜立;;一种基于R树和四叉树的移动对象空间数据库混合索引结构[J];计算机与数字工程;2006年03期

4 胡廷波;钟俊;;基于分簇的B~+树数据库索引优化算法[J];计算机应用;2013年09期

中国博士学位论文全文数据库 前1条

1 龙柏;并行计算平台上的数据索引技术研究[D];中国科学技术大学;2011年

中国硕士学位论文全文数据库 前3条

1 古毅;基于内容的图像检索中索引技术的研究及系统实现[D];重庆大学;2006年

2 郭娟;基于自适应聚类距离边界的高维检索算法研究[D];浙江工业大学;2012年

3 肖圆秀;云计算环境下海量GML空间数据存储索引机制研究[D];江西理工大学;2013年

，

本文编号：1072469