主讲人：郑卫国 

主讲人简介：郑卫国，复旦大学大数据学院青年研究员，博士生导师。主要从事图数据管理和计算、知识图谱构建和查询等相关理论研究工作，在国际顶级学术会议与期刊发表论文30余篇，其中包括SIGMOD、VLDB、ICDE、KDD、TODS、TKDE等，编写知识图谱专著1部；担任多个国内外重要学术会议的程序委员会主席或领域主席，包括GDMA、CCKS、NDBC；担任WISE 2021 演示共同主席（Demo Co-Chairs）；担任KDD、SIGMOD、VLDB、ICDE、WWW、AAAI、IJCAI、ICDM、CIKM、DASFAA 等国际知名会议程序委员会委员(Program Committee Member)；TKDE、VLDBJ、Information Systems、Information Sciences、WWW J、Data & Knowledge Engineering、DSE 等国际期刊审稿人

讲座摘要：对于图的任意两个顶点集，计算它们的公共顶点, 即集合求交，是三角形计数、极大团枚举、子图搜索等许多图算法的基础操作之一。因此，加速集合求交计算有利于提升下游很多算法的效率。在本报告中，我将介绍一种新的基于规约-归并的框架从而避免直接对两个集合求交。在规约阶段，不出现在公共点集中的节点可以基于区间规约的方式进行剪枝；经过修正后的子集可以直接应用归并算法求解。为了最大化整体规约和计算性能，将会形式化一个区间编码优化问题，证明其NP难的计算复杂度，最后设计有效的贪心算法进行求解。大量的实验证明所提出的算法对比基准算法在效率上有6-16倍左右的提升。

时间：2022.10.21（周五），上午10：00

地点：腾讯会议519-368-460