苟向阳关于滑动窗口模型下的图流上三角形近似计数的论文 《Sliding Window-based Approximate Triangle Counting over Streaming Graphs with Duplicate Edges》 被 SIGMOD 2021 接收。

由于很多图模型应用场景对于动态性的天然需求，图流分析近年来得到了越来越多的关注。由于图流规模大，更新速度快的特点，对其进行精确存储和分析从时间和空间上都有巨大的代价。相比之下高效的近似查询算法是一种更好的选择。此外，由于很多应用对于时效性的需求，降低图流中旧数据项的重要性，并在适当时机删除它们往往也是必需的。这种老化机制一般被描述为滑动窗口模型。然而，在滑动窗口模型下，对含重复边的图流进行近似三角形计数依然是一个有待解决的问题。本文中，我们提出了名为SWTC （Sliding Window Triangle Counting） 的算法。该算法使用独创策略来维护一个基于滑动窗口的无偏的，限定大小的样本，从而实现对滑动窗口内三角形数目的估算。实验表明该算法相比已有工作组合而成的基准算法，具有更高的准确度。