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

高维索引技术中向量近似方法研究

作　者: 崔江涛
导　师: 周利华
学　校: 西安电子科技大学
专　业: 计算机应用技术
关键词: 高维索引基于内容的图像检索维数灾难近似检索相关反馈向量近似方法主分量排序主分量R树矢量量化
分类号: TP391.4
类　型: 博士论文
年　份: 2005年
下　载: 491次
引　用: 10次
阅　读: 论文下载

内容摘要

基于内容的图像检索已经成为图像数据库的一项重要应用。高维数据索引是加速图像相似性检索的关键技术之一,也是多媒体和数据库领域的研究热点和难点。传统的多维索引技术在高维情况下会受到“维数灾难”现象的影响,在维数足够高的情况下(超过几十维),其检索性能会退化到最原始的顺序查找方法,研究有效的高维索引机制是使面向大规模数据库的检索达到实时性要求的关键。除了多媒体对象的相似性检索外,高维索引技术也可应用于其他相关领域,如数据挖掘、模式识别、机器学习、数据统计和分析等。本文在介绍维数灾难现象的基础上,系统地综述了高维索引技术的研究现状和发展趋势。向量近似方法是一种有效的高维索引技术,在高维情况下,其检索性能仍优于顺序查找方法,目前对高维索引技术的研究大部分都是在该方法的基础上进行。本文主要面向大规模图像数据库上k近邻搜索应用,在向量近似方法的基础上,开展对高维索引技术的研究。本论文的主要创新性成果如下所述:1.向量近似方法是一种基于压缩技术的索引方法,该方法需要顺序访问所有的近似向量才能完成搜索过程。提出了一种基于主分量排序的新型索引方法,只要顺序访问部分近似向量即可完成搜索过程。首先在正交变换域上建立近似向量,选择变换域能量最大的分量作为主分量,根据主分量值对近似向量进行顺序排列,并且用B+树存储每个数据页面中的主分量值的范围。在k近邻搜索过程中,采用变换域部分失真搜索算法,从初始访问数据页面开始在升序和降序两个方向上顺序访问近似向量。除了欧氏距离外,本文还将新的索引方法扩展到了二次式距离和绝对值距离。对于二次式距离,使用奇异值分解技术对向量进行变换。对于绝对值距离,提出了一种相邻元素相加的多分辨率数据结构。实验结果表明,该索引方法能够在保持顺序访问方式的基础上,减少近似向量访问数量,提高检索性能。2.提出了一种用R树组织近似向量的新型索引结构-PCR树。在正交变换域上建立近似向量,选择变换域能量最大的多维分量作为主分量,采用R树来组织主分量上的近似向量。在k近邻搜索过程中,采用了新的低维过滤算法来剪枝PCR树中的目录节点。主分量维数的选取对PCR树的索引能力影响很大,选取的主分量维数越少,能量损失越大,过滤效率越低,I/O开销会增大;选取的主分量维数越多,过滤效率越高,但是索引结构又会受到维数灾难现象的影响。实验结果表明,在PCR树中,访问很少的近似向量即可完成搜索过程,从而大幅度降低了搜索过程中的CPU运算开销。3.提出一种基于矢量量化技术的索引方法。从量化技术角度来看,近似向量

全文目录

第一章绪论  13-25
  1.1 课题的目的和意义  13-15
    1.1.1 基于内容的图像检索  13-15
    1.1.2 图像检索面临的主要问题  15
  1.2 多维索引技术  15-17
  1.3 高维索引技术发展趋势  17-22
    1.3.1 向量近似方法  17-19
    1.3.2 近似检索方法  19-21
    1.3.3 并行索引方法  21-22
  1.4 本文的的主要研究内容和章节安排  22-25
第二章高维数据索引技术的预备知识  25-37
  2.1 相似性搜索基本定义  25-28
    2.1.1 特征数据库  25
    2.1.2 距离度量方式  25-26
    2.1.3 查询类型  26
    2.1.4 向量空间与度量空间  26-27
    2.1.5 精确查询与近似查询  27-28
  2.2 向量空间中的高维特性  28-29
  2.3 维数灾难现象  29-35
    2.3.1 多维索引的结构  30
    2.3.2 多维索引的管理  30-31
    2.3.3 查询代价模型  31-32
    2.3.4 维数灾难现象的产生  32-34
    2.3.5 向量近似方法原理  34-35
  2.4 高维索引技术评价准则  35-36
  2.5 小结  36-37
第三章基于主分量排序的向量近似方法  37-63
  3.1 引言  37-38
  3.2 VA 方法及其改进算法  38-44
    3.2.1 索引结构  38-43
    3.2.2 近邻搜索算法  43-44
  3.3 欧氏距离上基于小波变换的多分辨率高维索引方法  44-48
    3.3.1 索引结构  45-46
    3.3.2 近邻搜索算法  46-48
  3.4 绝对值距离上的多分辨率高维索引方法  48-51
    3.4.1 索引结构  49-50
    3.4.2 近邻搜索算法  50-51
  3.5 二次式距离上基于SVD 的高维索引方法  51-54
    3.5.1 索引结构  52-53
    3.5.2 近邻搜索算法  53-54
  3.6 检索复杂性分析  54-55
  3.7 实验结果与分析  55-61
    3.7.1 实验环境  55-56
    3.7.2 欧氏距离上向量近似方法测试  56-58
    3.7.3 绝对值距离上向量近似方法测试  58-60
    3.7.4 二次式距离上向量近似方法测试  60-61
  3.8 小结  61-63
第四章采用树型索引结构的向量近似方法  63-77
  4.1 引言  63-64
  4.2 相关索引结构  64-67
  4.3 PCR 树索引结构  67-70
  4.4 近邻搜索算法  70-72
  4.5 检索复杂性分析  72-73
  4.6 实验结果与分析  73-76
  4.7 小结  76-77
第五章基于矢量量化的向量近似方法  77-95
  5.1 引言  77-78
  5.2 矢量量化技术  78-81
    5.2.1 矢量量化原理  78-79
    5.2.2 码书设计算法  79-81
  5.3 基于矢量量化技术的索引结构  81-85
    5.3.1 数据组织形式  81-83
    5.3.2 改进的矢量量化算法  83-84
    5.3.3 码书长度分析与乘积码书法  84-85
  5.4 近邻搜索算法  85-87
  5.5 检索复杂性分析  87-88
  5.6 实验结果与分析  88-93
    5.6.1 胞腔表示区域对过滤性能的影响  89-90
    5.6.2 码字长度对过滤性能的影响  90
    5.6.3 乘积码书数量对过滤性能的影响  90-91
    5.6.4 数据集大小对过滤性能的影响  91-92
    5.6.5 VA 方法与VQ 方法性能比较与分析  92-93
  5.7 小结  93-95
第六章向量近似方法在相关反馈技术中的应用  95-103
  6.1 引言  95
  6.2 向量近似方法在相关反馈技术中的应用  95-99
    6.2.1 二次式距离方法  95-97
    6.2.2 核函数方法  97-99
  6.3 改进的近邻搜索算法  99-101
  6.4 实验结果与分析  101-102
  6.5 小结  102-103
第七章向量近似方法在近似检索中的应用  103-121
  7.1 引言  103-104
  7.2 近似检索技术综述  104-113
    7.2.1 减少数据访问量的近似检索方法  104-108
    7.2.2 降低数据表示长度的近似检索方法  108-112
    7.2.3 近似检索的评价准则  112-113
  7.3 改进的基于矢量量化的近似检索方法  113-114
  7.4 向量近似方法中的近似近邻查询方法  114-117
  7.5 PCR 树的近似近邻查询方法  117-120
  7.6 小结  120-121
第八章总结与展望  121-125
参考文献  125-135
致谢  135-137
攻博期间的研究论文和参加的科研项目  137-139

高维索引技术中向量近似方法研究

内容摘要

全文目录

相似论文