苟向阳的论文 “Fast and Accurate Graph Stream Summarization” 被 ICDE 2019 录用。

图流是由数据项组成的序列，每一个数据项表示图中的一条边。这个序列形成了一个不断变化的动态图。图流在网络安全，社交网络分析，分布式系统故障检测等领域中都由大量的应用。由于图流数据量大，更新速度快，传统数据结构如邻接列表和邻接矩阵都不能有效存储它。但幸运的是，我们在存储图流时可以接受微小可控的误差，而不一定要完全精确存储。因此，在有限空间内用较高的速度对图流进行摘要是一种较为理想的选择。然而传统的摘要算法，不是支持的查询过于有限（如CM sketch 和 gSketch）就是精确度太低 （如TCM 和gMatrix）。我们提出了新的摘要算法 Graph Stream Sketch (GSS)，能用较小的空间对图流进行高速摘要，支持图上的大部分查询并具有高精确度。理论分析和实验测试都表明我们的算法远优于已有的摘要算法。