(辽宁大学信息学院 沈阳 110036) (zhangxin1979@hotmail.com)
出版日期: 2019-03-01基金资助:国家自然科学基金项目(U1811261,61802160)；辽宁省公共舆情与网络安全大数据系统工程实验室基金项目(2016-294)Spanner Algorithm for Directed Graph Stream
Zhang Xin, Li Xiaoguang(College of Information, Liaoning University, Shenyang 110036)
Online: 2019-03-01摘要/Abstract
摘要： 随着社交网络、交通网络、生物信息网等领域的分析需求快速增长,大规模图数据的处理逐渐成为信息技术领域新的挑战.近似覆盖图技术可以通过选取原图的子图,同时保证子图中任意节点间距离的增加在覆盖因子的约束范围内,从而降低大规模图存储与计算开销.当前相关工作主要研究无向图的近似覆盖图技术,针对于此,提出一种有向近似覆盖图算法,重新定义了簇集以及簇边、桥边、自由边3类关建边,并理论分析基于3类关键边的(3,2)近似覆盖图构建正确性.在此基础上,给出图数据以流模式到达时的近似覆盖图计算算法.算法通过判断边端点的类型进行边的积累聚簇及更新,进而得到全图近似覆盖结果,算法空间复杂度为O(n\+2/4).最后以基于幂率模型的人工数据集为实验对象,验证算法满足覆盖因子(3,2)的有向近似覆盖图定义,且空间与时间开销较小.
参考文献
相关文章 15
| [1] | 汤嘉武, 郑龙, 廖小飞, 金海. 面向高性能图计算的高效高层次综合方法[J]. 计算机研究与发展, 2021, 58(3): 467-478. |
| [2] | 杜明, 杨云, 周军锋, 陈子阳, 杨安平. 标签约束可达查询的高效处理方法[J]. 计算机研究与发展, 2020, 57(9): 1949-1960. |
| [3] | 朱颖雯, 陈松灿. 基于随机投影的高维数据流聚类[J]. 计算机研究与发展, 2020, 57(8): 1683-1696. |
| [4] | 王飞,钱铁云,刘斌,彭智勇. 支持范围查询的低冗余知识图谱管理[J]. 计算机研究与发展, 2019, 56(8): 1758-1771. |
| [5] | 向陶然，叶笑春，李文明，冯煜晶，谭旭，张浩，范东睿. 基于细粒度数据流架构的稀疏神经网络全连接层加速[J]. 计算机研究与发展, 2019, 56(6): 1192-1204. |
| [6] | 李振，汤战勇，李政桥，王海，龚晓庆，陈峰，陈晓江，房鼎益. 一种跨APP组件间隐私泄露自动检测方法[J]. 计算机研究与发展, 2019, 56(6): 1252-1262. |
| [7] | 欧焱, 冯煜晶, 李文明, 叶笑春, 王达, 范东睿. 面向数据流结构的指令内访存冲突优化研究[J]. 计算机研究与发展, 2019, 56(12): 2720-2732. |
| [8] | 胡智尧,李东升,李紫阳. 数据中心网络流调度技术前沿进展[J]. 计算机研究与发展, 2018, 55(9): 1920-1930. |
| [9] | 王珊珊,刘万军,肖成龙. 可扩展处理器中最大凸自定义指令迭代识别研究[J]. 计算机研究与发展, 2018, 55(7): 1584-1596. |
| [10] | 刘炳涛,王达,叶笑春,范东睿,张志敏,唐志敏. 基于数据流块的空间指令调度方法[J]. 计算机研究与发展, 2017, 54(4): 750-763. |
| [11] | 黎建辉,沈志宏,孟小峰. 科学大数据管理：概念、技术与系统[J]. 计算机研究与发展, 2017, 54(2): 235-247. |
| [12] | 闻英友,王少鹏,赵宏. 界标窗口下数据流最大规范模式挖掘算法研究[J]. 计算机研究与发展, 2017, 54(1): 94-110. |
| [13] | 杨超,陈海燕,刘胜. 一种支持变形基2\+4 FFT的4路并行访存方法[J]. 计算机研究与发展, 2017, 54(1): 134-141. |
| [14] | 刘炳涛,王达,叶笑春,张浩,范东睿,张志敏. 一种缓存数据流信息的处理器前端设计[J]. 计算机研究与发展, 2016, 53(6): 1221-1237. |
| [15] | 毕安琪,董爱美,王士同. 基于概率和代表点的数据流动态聚类算法[J]. 计算机研究与发展, 2016, 53(5): 1029-1042. |
PDF全文下载地址:
https://crad.ict.ac.cn/CN/article/downloadArticleFile.do?attachType=PDF&id=3895
