流式鲁棒子模覆盖算法的图集覆盖问题的研究  

Study on the graph cover problem of streaming robust submodular cover algorithm

作　　者：田歌 王耀力 常青 孙永明[2] TIAN Ge;WANG Yaoli;CHANG Qing;SUN Yongming(School of Information and Computer,Taiyuan University of Technology,Jinzhong 030600,China;Shanxi Academy of Forest Sciences,Taiyuan 030000,China)

机构地区：[1]太原理工大学信息与计算机学院,山西晋中030600 [2]山西省林业科学研究院,山西太原030000

出　　处：《电子设计工程》2021年第23期133-138,共6页Electronic Design Engineering

基　　金：国家自然科学基金资助项目(61828601);山西省自然科学基金资助项目(201801D121141)。

摘　　要：针对在具有庞大数据集的图中选择小部分具有代表性顶点的问题,将其归纳为数据摘要问题,并采用传统子模覆盖的方法来解决。对庞大数据集进行动态处理时,为保证因数据集过大而无法装入内存的同时还要对数据集中所有数据进行访问,引入了流式算法,与子模覆盖算法结合后,对其进行改进使选出的集合具有鲁棒性,并将该算法的边界和通信复杂度与之前算法比较。经仿真实验得出,文中算法不仅能避免对大量内存进行有效的访问,而且可以在删除部分元素后,集合稳定性比普通流式子模算法提高10%以上。Aiming at the problem of selecting a small part of representative vertices in a graph with a huge data set,it is summarized as a data summary problem,and the traditional submodular covering method is used to solve it.When dynamically processing a huge data set,in order to ensure that the data set is too large to be loaded into the memory and access to all the data in this data set,a streaming algorithm is introduced.After combining with the submodular covering algorithm,its improvement is used to make selected set robust,and the boundary and communication complexity of this algorithm are compared with the previous algorithms.Through simulation experiments,it is concluded that the algorithm in this paper can not only avoid effective access to a large amount of memory,but also after deleting some elements,the set stability is improved by more than 10%compared with the ordinary streaming submodular algorithm.

关 键 词：数据摘要 集合覆盖 子模优化 流算法 鲁棒性 

分 类 号：TN911.1[电子电信—通信与信息系统]