实验室动态

[2021 SIGMOD] Sliding Window-based Approximate Triangle Counting over Streaming Graphs with Duplicate Edges

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

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