高维索引作为模式识别、内容检索等领域的关键技术,其目的在于建立特征库的索引结构提高特征向量查询效率,但其在高维情况下存在的“维度灾难”问题一直困扰着高维特征向量查询的性能提升。自上世纪六七十年代起,研究人员提出了许多种类的高维索引解决方案,但迄今仍然没有出现一种在各方面性能都能令人满意的索引技术,相关领域对良好的高维索引技术的需求仍然迫切。本文受复杂网络中“六度分隔”现象的启发,设计了一种基于小世界模型的新型高维索引技术,并给出了相应的范围查询,近似k近邻查询和索引维护算法。该索引维护一定的邻居节点分布,包括近邻连接和远程连接,并将高维索引中向量查询的过程类比于图上邻居节点间的跳跃,通过逐跳地往目标方向逼近最终找到目标节点,因此该索引被命名为逐跳逼近索引。同时,通过对相关理论研究证明的总结,本文对该索引模型作了展开分析,说明了在简化模型上其查询平均路径长度的理论上界。最后,本文进一步提出了若干基于小世界模型的组合索引方案,并结合数据库系统将上述高维索引推向实际应用。具体而言,本文的详细工作包括：第一,本文参照小世界网络的理论研究成果,对项目组的逼近索引结构进行了多项改进：额外添加了一定比例的随机远程连接,以提供远程跳跃的捷径,进一步提高了索引查询性能；取消范围限制稳定各节点的度,以保证图在各种实际情况中的连通性,从而使得索引能够较好地处理数据分布不均和小库容量等实际应用中常见的查询场景。第二,本文进一步完善了逐跳逼近索引的范围查询和近似kNN查询算法以及索引维护算法,并将该索引应用于随机生成库及实际图像特征库。结合理论分析和实验数据,探讨了逐跳逼近索引的关键参数性质特点,以及应用到不同场景时的预期效果和注意事项。第三,最后,本文分析了逐跳逼近索引的优点和不足,结合目前已有的高维索引技术,给出了若干分层组合索引的算法。此外,为推动该索引更快的应用于实际系统,提出了结合数据库系统的逐跳逼近索引应用,借助成熟的数据库系统解决了算法分布式拓展和内存缓存管理等多个实际运用问题。相关理论分析表明,本文算法适合用于处理高维度及各种容量特征库的相似性查询,具有访问特征库记录条数少,查询准确性高等特点。实验结果表明,数据访问比例为10%以下且准确度为90%以上,同时随着库容量增大,访问比例降低而准确度基本不变。