王选所师生参加SIGMOD2021

2021年6月20日至25日SIGMOD数据管理国际会议(Special Interest Group on Management Of Data)在中国西安召开,北京大学王选计算机研究所数据管理研究室邹磊老师、博士生苟向阳、胡琳参加了此次会议。

SIGMOD数据管理国际会议是由美国计算机协会(ACM)数据管理专业委员会(SIGMOD)发起、在数据库领域具有最高学术地位的国际性学术会议。会议通常于每年6月进行,吸引了全球范围内数据库领域的研究者、从业者、开发者和用户共同探索前沿课题和成果,交流技术、工具和经验,引导和促进数据库学科的发展。

王选所师生在本次SIGMOD2021会议上发表2篇长文,论文具体信息如下:

[1] Xiangyang Gou, Lei Zou:Sliding Window-based Approximate Triangle Counting over Streaming Graphs with Duplicate Edges. SIGMOD Conference 2021: 645-657

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

 [2] Lin Hu, Lei Zou, Yu Liu:Accelerating Triangle Counting on GPU. SIGMOD Conference 2021: 736-748

三角形计数是图上的重要算法,它是图上的许多其他算法例如k-core和k-truss的基础。随着要处理的图的规模的增加,近些年许多工作尝试通过将三角形计数移植到GPU上来实现更好的性能。我们发现图上的预处理策略,例如边的方向的确定和点的重新排序,对于许多三角形计数的算法都有非常大的影响。因而我们想设计一个预处理策略,在不改变已有的各种算法的具体实现的前提下,对于它们的性能都有提升。我们首先从当前最优的算法中抽取出通用的计算模式,在此之上构建算法的运行模型;然后我们给出对于运行模型的定量分析,以便准确描述这些预处理策略对性能的影响;接下来,我们基于定量分析给出预处理的具体方案。最终我们的预处理策略对于当前最优的GPU上的三角形计数算法都有非常大的性能提升。

SIGMOD 2021期间,邹磊教授受邀参加Enterprise Database Technology and Ecosystem Development WORKSHOP, 做了题为 “Noah: Neural-Optimized A* Search Algorithm for Graph Edit Distance Computation” 的学术报告,报告中介绍了北大王选所数据管理实验室最近研究成果,将图神经网络技术融入到传统的A*搜索算法,用于解决图编辑距离等计算难问题,有效地提高了计算的速度。

 

CLOSE

上一篇 下一篇