Abstract: High-dimensional indexing is a key technique in content based retrieval and pattern recognition field, and the performance of it affects the retrieval speed and accuracy directly, but Curse of Dimensionality hinders the improvement of it. This paper proposes a high-dimensional indexing technology based on graph which uses small world model as design idea. During the range and the approximate neighbor query, this method gradually approximates the query focuses to the hit area. Experiment demonstrates that this method can handle with the retrieval of high-dimensional data vectors effectively without prior distribution knowledge. And the maintainability and expansibility of this system is also good.

Key words: high-dimensional indexing, small world model, range query, similarity search

摘要： 高维索引作为基于内容检索和模式识别等领域的一项关键技术，其性能直接影响整个系统的查询速度和准确率，但高维情况下的 “维度灾难”一直制约着相应检索性能的提高。通过分析小世界模型，提出了完整的逐跳逼近索引算法，该算法仅维护点与点在度量空间上的局部邻近关系，通过将查询过程的“关注点”逐步往查询命中区域跳跃逼近来实现高维空间数据点间的范围查询和近似近邻查询。实验证明该方法在不依赖索引数据的先验分布情况下能有效地处理高维数据向量的检索，且具有良好的可维护性与拓展性。

关键词: 高维索引, 小世界模型, 范围查询, 相似性查询