基于γ空间划分的高维数据索引结构研究

论文摘要

传统的高维数据索引结构在维度较高的情况下,其检索效率甚至会低于最原始的顺序查找方法,即所谓的“维度灾难”。在高维数据空间,“维度灾难”现象主要是由空间划分策略引起的。空间划分的不恰当,导致索引结构的不合理,进而使其索引结构的性能下降。针对上述问题,本文做了如下工作:首先根据在高维数据空间中无效的信息在低维空间中往往无效的原理,通过采用γ划分策略沿着关键维对高维数据空间中的数据进行降维、聚类,提出了一种压缩金字塔技术;其次,给出了压缩金字塔技术的基本概念、划分策略、构造方法以及相应的点查询、范围查询、KNN查询算法;最后,通过对维度不同、数据集大小不同的真实数据进行实验,得出如下结论:压缩金字技术改善了金字塔技术在偏斜数据空间存在的“损失的空间邻接性”、“假命中”等问题,因此在高维稀疏空间进行范围查询和KNN查询时,与金字塔技术相比,具有良好的查询性能,是高维数据空间一种有效的高维索引结构。

论文目录

• 摘要
• Abstract
• 1 引言
• 1.1 研究背景和意义
• 1.2 国内外研究现状
• 1.3 研究目标及主要贡献
• 1.3.1 研究目标
• 1.3.2 主要贡献
• 1.4 论文结构及主要内容
• 2 高维数据索引结构的理论基础
• 2.1 引言
• 2.2 高维数据及其索引结构特点
• 2.2.1 高维数据特点
• 2.2.2 高维数据索引结构特点
• 2.2.3 “维数灾难”现象的产生
• 2.3 高维数据查询方式
• 2.3.1 相似性度量
• 2.3.2 高维数据库的查询方式
• 2.4 向量空间高维索引结构
• 2.4.1 向量空间高维索引结构分类
• 2.4.2 KDB-Tree
• 2.4.3 R-Tree 及其变种
• 2.4.4 量化近似类
• 2.4.5 金字塔技术
• 2.4.6 聚类金字塔技术
• 2.5 度量空间高维索引结构
• 2.5.1 度量空间高维索引结构分类
• 2.5.2 BK-Tree
• 2.5.3 M-Tree
• 2.5.4 SLIM-Tree
• 2.5.5 VP-Tree
• 2.5.6 向量空间与度量空间索引结构异同点
• 2.6 小结
• 3 压缩金字塔技术
• 3.1 引言
• 3.2 压缩金字塔的基本概念
• 3.3 γ空间划分的过程
• 3.3.1 关键维的选择
• 3.3.2 γ空间划分的过程
• 3.3.3 γ空间的标识
• 3.4 压缩金字塔技术的基本操作
• 3.4.1 压缩金字塔的构造
• 3.4.2 插入操作
• 3.4.3 删除操作
• 3.5 压缩金字塔技术的查询操作
• 3.5.1 点查询
• 3.5.2 范围查询
• 3.5.3 KNN 查询
• 3.6 小结
• 4 压缩金字塔技术性能分析
• 4.1 引言
• 4.2 索引结构性能分析
• 4.2.1 理论分析
• 4.2.2 实验分析
• 4.3 检索性能分析
• 4.3.1 点查询性能对比
• 4.3.2 范围查询性能对比
• 4.3.3 KNN 查询性能对比
• 4.4 小结
• 5 结论
• 参考文献
• 致谢
• 攻读硕士学位期间发表的学术论文及参加科研工作