学位论文 > 优秀研究生学位论文题录展示

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

作　者: 王淑娥
导　师: 孙劲光
学　校: 辽宁工程技术大学
专　业: 计算机应用技术
关键词: 高维数据索引维数灾难空间划分策略 γ划分策略关键维压缩金字塔
分类号: TP311.13
类　型: 硕士论文
年　份: 2008年
下　载: 20次
引　用: 0次
阅　读: 论文下载

内容摘要

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

全文目录

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

相似论文

基于数据挖掘的社区网站用户行为分析系统,TP393.092
基于认知模型的运动人手三维跟踪方法研究,TP391.41
基于流形学习与子空间的降维方法研究与应用,TP391.41
数据降维技术的建模研究与应用,TP391.41
美式分红篮子看涨期权定价方法研究,F224
对液相质谱数据集的数据降维,TP18
零售企业竞争力构成及演化研究,F717
图像检索中的特征表示和索引方法的研究,TP391.41
高维数据索引及其查询处理技术研究,TP311.13
基于Bayes方法和图限制下正规化方法的变量选择问题及其在基因组数据中的应用,O212.1
国防高新技术企业持续创新管理研究,F426.48
神经模糊系统研究及其在电厂协调系统中的应用,TK323
企业能力的维度、层次及层次演进研究,F224
高维索引技术中向量近似方法研究,TP391.4
战略执行系统分析与优化研究,F272
支持XML数据查询的F&B索引结构的研究,TP311.13
海量多数据库集成系统的查询处理研究,TP311.13
基于BAP的数据压缩、操作与查询处理系统的实现,TP311.13
基于分治法的聚类方法研究,TP311.13
PG炼钢厂MES系统数据挖掘的设计与开发,TP311.13
基于数据挖掘聚类技术的我国高校分类研究,TP311.13