计算机工程与应用 ›› 2015, Vol. 51 ›› Issue (16): 136-141.

• 数据库、数据挖掘、机器学习 • 上一篇    下一篇

基于小世界模型的高维索引算法

桂舒婷,郑  烇,周乐乐,刘  欣,王  嵩   

  1. 中国科学技术大学 信息科学技术学院 自动化系,合肥 230027
  • 出版日期:2015-08-15 发布日期:2015-08-14

High-dimensional indexing technology based on small-world model

GUI Shuting, ZHENG Quan, ZHOU Lele, LIU Xin, WANG Song   

  1. School of Information and Technology, University of Science and Technology of China, Heifei 230027, China
  • Online:2015-08-15 Published:2015-08-14

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

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

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