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

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