图数据流的模型、算法和系统

李友焕; 邹磊

doi:10.11959/j.issn.2096-0271.2018039

您当前的位置：

首页 >

文章列表页 >

图数据流的模型、算法和系统

专题：大数据驱动的智能计算体系架构 | 更新时间：2024-06-03

- 图数据流的模型、算法和系统
- Graph stream:model,algorithm and system
- 大数据 2018年4卷第4期页码：2018039
- 作者机构：
- 作者简介：
  
  [ "李友焕（1991-），男，北京大学计算机科学技术研究所博士生，主要研究方向为图数据流的管理、数据流算法、社交网络分析等。" ]
  [ "邹磊（1981-），男，北京大学计算机科学技术研究所教授、博士生导师，主要研究方向为海量图数据的管理、基于图的RDF知识库数据管理、图数据库、知识图谱构建与应用等。" ]
- 基金信息：
- DOI：10.11959/j.issn.2096-0271.2018039
  中图分类号： TP315
- 网络首发：2018-07，
  
  纸质出版：2018-07-15
- 稿件说明：
移动端阅览
李友焕, 邹磊. 图数据流的模型、算法和系统[J]. 大数据, 2018,4(4):2018039.

Youhuan LI, Lei ZOU. Graph stream:model,algorithm and system[J]. Big Data Research, 2018, 4(4): 2018039.
李友焕, 邹磊. 图数据流的模型、算法和系统[J]. 大数据, 2018,4(4):2018039. DOI： 10.11959/j.issn.2096-0271.2018039.

Youhuan LI, Lei ZOU. Graph stream:model,algorithm and system[J]. Big Data Research, 2018, 4(4): 2018039. DOI： 10.11959/j.issn.2096-0271.2018039.

摘要

在应用数据高速增长的场景下，已有的静态图计算的模型和方法难以应对数据高速更新的挑战，图数据流模型应运而生。首先讨论当前大规模复杂数据流的产生及其管理需求，分析静态图模型以及已有数据流算法、系统在应对这一数据流场景的固有缺陷，阐述图数据流模型产生的重要背景。然后通过总结分析早期图的流式计算以及已有的少量图数据流的研究工作，给出图数据流模型的一般定义。最后，从方法和问题两个角度探讨图数据流的研究前景，并简要介绍图数据流管理系统相关技术架构。

Abstract

In the scenario where data of real-world applications is in high-speed growth

existing methods for static graph computation are hard to approach the challenges from the rapidly updated data

and graph stream model arise at the historic moment.The inherent defects of static graph model and exiting data stream algorithms/systems over high-speed graph-structured data were discussed

and then the formal definition of graph stream combining with previous similar models was presented.Some promising research problems and applications over graph stream were probed

and then the possible requirements and technique issues on graph stream management system (GSMS) were looked into the future.

关键词

Keywords

references

ANGEL A , KOUDAS N , SARKAS N , et al . Dense subgraph maintenance under streaming edge weight updates for realtime story identification [J ] . VLDB Journal , 2014 , 23 ( 2 ): 175 - 199 .

SAKAKI T , . Earthquake shakes Twitter users:real-time event detection by social sensors [C ] // The 19th International Conference on World Wide Web,April 26-30,2010,Raleigh,USA . New York:ACM Press , 2010 : 851 - 860 .

TOSHNIWAL A , TANEJA S , SHUKLA A , et al . Storm@Twitter [C ] // The 2014ACM SIGMOD International Conference on Management of Data,June 22-27,2014,Snowbird,USA . New York:ACM Press , 2014 : 147 - 156 .

BAR-YOSSEFF Z , KUMART R , SIVAKUMAR D . Reductions in streaming algorithms,with an application to counting triangles in graphs [C ] // The 13th Annual ACM-SIAM Symposium on Discrete Algorithms,January 6-8,2002,San Francisco,USA . Philadelphia:Society for Industrial and Applied Mathematics , 2002 : 623 - 632 .

JOWHARI H , GHODSI M . New streaming algorithms for counting triangles in graphs [C ] // The 11th Annual International Conference,August 16-19,2005,Kunming,China.[S.l.:s.n] . 2005 : 710 - 716 .

BURIOL L S , FRAHLING G , LEONARDI S , et al . Counting triangles in data streams [C ] // The 25th ACM SIGMODSIGACT-SIGART Symposium on Principles of Database Systems,June 26-28,2006,Chicago,USA . New York:ACM Press , 2006 : 253 - 262 .

UNEL G , FISCHER F , BISHOP B . Answering reachability queries on streaming graphs [C ] // The 1st International Workshop Stream Reasoning,May 31,2009,Heraklion,Greece.[S.l.:s.n] . 2009 .

DEMETRESCU C , FINOCCHI I , RIBICHINI A . Trading off space for passes in graph streaming problems [J ] . ACM Transactions on Algorithms , 2006 , 6 ( 1 ): 1 - 17 .

MCGREGOR A . Graph stream algorithms:a survey [J ] . ACM SIGMOD Record , 2014 , 43 ( 1 ): 9 - 20 .

SONG C Y , GE T , CHEN C , et al . Event pattern matching over graph streams [J ] . Proceedings of the VLDB Endowment , 2014 , 8 ( 4 ): 413 - 424 .

FAN W F , WANG X , WU Y , et al . Incremental graph pattern matching [J ] . ACM Transactions on Database Systems , 2013 , 38 ( 3 ): 925 - 936 .

CHOUDHURY S , HOLDER L , CHIN G , et al . A selectivity based approach to continuous pattern detection in streaming graphs [J ] . Computer Science , 2015 , 93 ( 8 ): 939 - 945 .

AGGARWAL C C , LI Y , YU P S , et al . On dense pattern mining in graph streams [J ] . Proceedings of the VLDB Endowment , 2010 , 3 ( 1-2 ): 975 - 984 .

VALARI E , KONTAKI M , PAPADOPOULOS A N . Discovery of top-k dense subgraphs in dynamic graph collections [C ] // The 24th International Conference on Scientific and Statistical Database Management,June 25-27,2012,Chania,Greece . Heidelberg:Springer , 2012 : 213 - 230 .

CHI Y , WANG H , YU P S , et al . Moment:Maintaining closed frequent itemsets over a stream sliding window [C ] // The 4th IEEE International Conference on Data Mining,November 1-4,2004,Brighton,UK . Piscataway:IEEE Press , 2004 : 59 - 66 .

SOLOMON M M . Algorithms for the vehicle routing and scheduling problems with time window constraints [J ] . Operations Research , 1987 , 35 ( 2 ): 254 - 265 .

RODITTY L , ZWICK U . A fully dynamic reachability algorithm for directed graphs with an almost linear update time [J ] . SIAM Journal on Computing , 2016 , 45 ( 3 ): 712 - 733 .

SCHANK T , WAGNER D . Finding,counting and listing all triangles in large graphs,an experimental study [C ] // The 36th Annual ACM Symposium on Theory of Computing,June 13-16,2004,Chicago,USA . Heidelberg:Springer , 2005 : 606 - 609 .

KOLOUNTZAKIS M N , MILLER G L , PENG R , et al . Efficient triangle counting in large graphs via degree-based vertex partitioning [J ] . Internet Mathematics , 2012 , 8 ( 1-2 ): 161 - 185 .

ZILIASKOPOULOS A K , MAHMASSANI H S . Time dependent,shortest-path algorithm for real-time intelligent vehicle highway system applications [J ] . Transportation Research Record , 1993 ( 1408 ): 94 - 100 .

CLIMACO J C N , MARTINS E Q V . A bicriterion shortest path algorithm [J ] . European Journal of Operational Research , 1982 , 11 ( 4 ): 399 - 404 .

YUAN Y , WANG G , WANG H , et al . Efficient subgraph search over large uncertain graphs [J ] . Proceedings of the VLDB Endowment , 2011 , 4 ( 11 ): 876 - 886 .

YAN X , HAN J . gSpan:graph-based substructure pattern mining [C ] // The 2002 IEEE International Conference on Data Mining,December 9-12,2002,Maebashi City,Japan . Piscataway:IEEE Press , 2002 : 721 - 724 .

KASHIMA H , INOKUCHI A . Kernels for graph classification [C ] // The 2002 IEEE International Conference on Data Mining,December 9-12,2002,Maebashi City,Japan.Piscataway:IEEE Press,2002.Maebashi City,Japan . Piscataway:IEEE Press , 2002 .

SCHAEFFER S E . Graph clustering [J ] . Computer Science Review , 2007 , 1 ( 1 ): 27 - 64 .

浏览量

840

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

暂无数据