Computer Engineering and Applications ›› 2016, Vol. 52 ›› Issue (11): 77-83.

Previous Articles     Next Articles

Research on updates for high-dimensional indexing technology based on small-world model

ZHOU Lele1,2,3, ZHENG Quan1,2,3, WANG Song1, YANG Jian1, YANG Zhiwei1,2,3   

  1. 1.Department of Automation, School of Information Science and Technology, University of Science and Technology of China, Hefei 230027, China
    2.Key Laboratory of Wireless-Optical Communications, Chinese Academy of Sciences, Hefei 230026, China
    3.School of Information Science and Technology, University of Science and Technology of China, Hefei 230026, China
  • Online:2016-06-01 Published:2016-06-14

基于小世界模型的高维索引更新维护算法研究

周乐乐1,2,3,郑  烇1,2,3,王  嵩1,杨  坚1,杨志伟1,2,3   

  1. 1.中国科学技术大学 信息科学技术学院 自动化系,合肥 230027
    2.中国科学院 无线光电通信重点实验室,合肥 230026
    3.中国科学技术大学 信息科学技术学院,合肥 230026

Abstract: High-dimensional indexing based on small-world model can effectively deal with the retrieval problem of high-dimentional data. But the insertion and deletion algorithms are not efficient. This limits its uses. By analyzing the theoretical model of the indexing structure, a novel insertion and deletion algorithms is proposed to maintain the indexing structure of small-world properties. The insertion algorithm is modeled as a growing network model. Its degree distribution is analyzed by mean-field approach, clustering coefficient and average shortest path length by experiment. Theoretical analysis and the experimental results show that the insertion and deletion algorithms can not only update the indexing structure but also ensure the small-world properties. This extends the scope of application of this indexing technology.

Key words: high-dimensional indexing, small-world model, growing network model, degree distribution, insertion, deletion

摘要: 基于小世界模型的高维索引技术能有效地处理高维数据的检索问题,但对适合该索引结构的插入和删除算法没有进行深入研究,影响了其应用范围。在深入分析该索引结构理论模型的基础上,提出了能够维护索引结构小世界特性的迭代式插入和删除算法。通过将插入算法建模成一种网络增长模型,应用平均场理论分析其度分布,通过实验测得聚集系数及平均路径长度,理论分析和实验结果表明插入和删除算法在完成更新时可以保证索引结构仍然符合小世界特性,扩展了该索引技术的应用范围。

关键词: 高维索引, 小世界模型, 网络增长模型, 度分布, 插入, 删除