高维索引是基于内容的多媒体检索及地理、生物数据库等需要运用到高维数据库的系统中一个至关重要的部分，其性能直接影响整个查询系统的查询速度和准确率，但高维情况下的“维度灾难”问题始终困扰着高维特征向量查询的性能提升，使得高维索引常常成为相关系统的性能瓶颈之一。自上世纪六七十年代起，研究人员提出了许多种类的高维索引解决方案，但迄今仍然没有出现一种各方面性能都能令人满意的索引技术，使得当前高维索引技术的发展仍然纷乱而迫切。　　 本文参考目前热门的图上的随机游走算法，设计了一种融入了图上游走思想的新型高维索引技术，称为逼近索引，并给出了相应的逼近游走相似性查询算法。同时，通过分析逼近游走算法和一般高维索引算法的优缺点，本文进一步提出了一套基于逼近游走的分层组合索引思想，并按照此思想给出了一种新的相似逼近索引算法。具体而言，本文的详细工作包括:　　 第一，本文分析总结了向量空间和度量空间中的各种常见索引结构的基本思想和优缺点，阐述了高维索引算法的发展趋势。然后融合向量空间和度量空间索引特点，设计了一种不与特征向量维度直接相关，能有效减少高维向量查询中对特征向量库访问比例的逼近索引及相关相似性查询算法。该索引将高维特征向量库表示成图的形式，引入逼近游走来进行近似近邻查询和范围查询。　　 第二，本文进一步分析了目前逼近索引算法的优点和不足之处，联合多种现有的高维索引和逼近索引，提出了一种基于逼近索引的多层组合索引算法的思路。其中，完整地给出了近似逼近索引的生成维护及查询算法，并对该索引的综合性能进行了详细的评测。此外，对于超高维数据，本文提出了包含向量降维和一维转换算法的组合索引设想。　　 第三，在向量降维部分，本文引入了近年来热门的压缩感知理论，设计了一种利用压缩采样的思想进行高维向量降维的线性降维算法。该算法具有需要信息少，计算时间和空间复杂度低以及能处理特别高维度向量的特点。　　 实验数据表明，本文算法适合应用于大型特征库的相似性查询，具有访问特征库中记录条数少，查询准确性高的特点，综合性能要优于近期提出的多个索引算法，对高维索引技术的发展具有很好的参考价值。