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