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

2016,52(11)Computer Engineering and Applications 计算机工程与应用1引言随着多媒体技术和互联网的发展,社交媒体和即时通信工具的迅速普及,以图像和视频为主的多媒体信息呈现爆炸式增长,这些数据具有海量和高维度的特征。如何有效管理和检索这些数据已成为亟待解决的难题。高维索引技术作为管理和检索这类高维海量数据的一种方式,得到广泛的研究。

高维索引是一种通过建立索引结构来提高数据库查询效率的技术,被大量应用于基于内容的图像和视频查询[1]。国内外的研究机构自1970年开始便对其进行了深入的研究,提出了多种高维索引结构,现在已经被推广应用到地理信息系统、生物信息数据库和遥感光谱基于小世界模型的高维索引更新维护算法研究

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

ZHOU Lele 1,2,3,ZHENG Quan 1,2,3,WANG Song 1,YANG Jian 1,YANG Zhiwei 1,2,3

1.中国科学技术大学信息科学技术学院自动化系,合肥230027

2.中国科学院无线光电通信重点实验室,合肥230026

3.中国科学技术大学信息科学技术学院,合肥230026

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 ZHOU Lele,ZHENG Quan,WANG Song,et al.Research on updates for high-dimensional indexing technology based on small-world model.Computer Engineering and Applications,2016,52(11):77-83.

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

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

文献标志码:A 中图分类号:TP311.12doi :10.3778/j.issn.1002-8331.1504-0245

基金项目:国家自然科学基金(No.61174062)。

作者简介:周乐乐(1990—),男,硕士,研究领域为高维索引、网络多媒体,E-mail :zhoulele1991@163.com ;郑烇(1970—),男,博

士,副教授,研究领域为网络多媒体及视频语义检索;王嵩(1975—),男,博士,讲师,研究领域为计算机网络;杨坚(1975—),男,博士,副教授,研究领域为网络系统建模、未来网络;杨志伟(1989—),男,硕士,研究领域为网络多媒体。收稿日期:2015-04-24修回日期:2015-06-23文章编号:1002-8331(2016)11-0077-07

CNKI 网络优先出版:2015-09-02,http://www.cnki.net/kcms/detail/11.2127.TP.20150902.1524.036.html

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

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

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

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

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

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

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

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

77

相关推荐
相关主题
热门推荐