报告题目：Graph Stream Summarization
报告人：Dr. Nan Tang
报告时间：2019年6月6日 下午14:00-15:00
报告地点：浑南校区信息B馆328学术报告厅
邀请人：必赢线路检测3003 必赢线路检测3003 于戈 教授
摘要：
A graph stream, which refers to the graph with edges being updated sequentially in a form of a stream, has important applications in cyber security and social networks. Due to the sheer volume and highly dynamic nature of graph streams, the practical way of handling them is by summa- rization. Given a graph stream G, directed or undirected, the problem of graph stream summarization is to summarize G as SG with a much smaller (sublinear) space, linear con- struction time and constant maintenance cost for each edge update, such that SG allows many queries over G to be approximately conducted eciently. The widely used practice of summarizing data streams is to treat each stream element independently by e.g., hash- or sample-based methods, with- out maintaining the connections (or relationships) between elements. Hence, existing methods can only solve ad-hoc problems, without supporting diversified and complicated analytics over graph streams. We present TCM, a novel graph stream summary. Given an incoming edge, it summarizes both node and edge information in constant time. Consequently, the summary forms a graphical sketch where edges capture the connections inside elements, and nodes maintain relationships across elements. We discuss a wide range of supported queries and establish some error bounds. In addition, we experimentally show that TCM can effectively and efficiently support analytics over graph streams beyond the power of existing sketches, which demonstrates its potential to start a new line of research and applications in graph stream management.
报告人简介：
Dr. Nan Tang is a senior scientist at Qatar Computing Research Institute (QCRI), HBKU, Doha, Qatar. Prior to joining QCRI in Dec 2011, He was a Research Fellow at LFCS (Laboratory for Foundations of Computer Science) at the University of Edinburgh, Edinburgh, UK (2010--2011). He was a scientific staff member with the CWI (Dutch National Research Center for Mathematics and Computer Science), Amsterdam, Netherlands (2008--2010). He got his PhD. degree from The Chinese University of Hong Kong, China (2007). He got his master and bachelor from Northeastern University, China, at 2001 and 2004, respectively. He holds a visiting position at University of Waterloo, Canada (03/2007-08/2007).
