报告人：严达

时的间：2022/06/13 上午10:00

主持人：邹磊 教授

报告摘要：

大图数据在很多业界的应用中已经非常普遍，包括社交网络，知识图谱，属性图（property graphs）等。传统的关系型数据依赖统一的关系代数（relational algebra）制定统一的运算符并对其进行优化，然而这一策略在图数据上并不合适，因为不同图操作之间的解决方法天差地别，例如基于随机游走的PageRank和SimRank，基于路径计算的最短路和可达性问题，基于模式匹配的子图同构问题和密集子图挖掘问题，基于数据挖掘算法的频繁子图挖掘问题，基于机器学习的图神经网络推理以及推荐系统等。然而目前主流的大图计算框架仍然是顶点式的（vertex-centric, or think like a vertex），而且很多底层执行设计只考虑如何突破单机存储限制以处理更大的图，却没有考虑到性能是否随着CPU核数而提高。对于某些图计算问题，当前的大数据系统方案获得的性能可能并不比串行的外存执行（out-of-core execution）算法快多少，使得绝大多数CPU资源处于浪费状态。

为了解决这些问题，我们提出了一个新的任务式（task-based, or think like a task）并行框架，称之为T-thinker。T-thinker框架能够有效利用CPU资源达到较为理想的加速比，并且我们已经基于该框架开发了3个不同的系统: (1) 用于从大图中挖掘子图（例如：子图匹配，密集子图挖掘）的G-thinker分布式编程框架（bit.ly/gthinker），(2) 用于挖掘频繁模式（子图，子树，子序列，子矩阵）的PrefixFPM并行框架，(3) 用于构建决策树ensemble模型的TreeServer系统。更多系统将在未来几年内被开发出来。本报告将介绍T-thinker框架以及其在图计算上的应用，并展望其与顶点式系统框架结合、作为针对大图的各种异构计算的统一解决方案的潜力。

报告人简介：

严达目前是阿拉巴马大学伯明翰分校计算机系的助理教授，本科毕业于复旦大学（2005-2009），博士毕业于香港科技大学（2009-2014）。由于他在大数据系统方向的贡献，他在2015年度被授予香港科学会青年科学家称号，是该奖项当年在Physical/Mathematical Science方向的唯一获奖者。他的研究被同行广泛引用并给予很高的评价，例如他开发的Blogel系统在VLDB 2018的一篇图系统实验比较论文中被评价为overall winner。这些系统也被大家广泛使用与引用，包括SIGMOD, VLDB, ICDE, IPDPS等顶会的论文，引用的团队包括IEEE/ACM Fellow以及图灵奖获得者带领的研究团队。在香港中文大学做博后期间（2014-2016），严达主要从事于改进Google's Pregel系统在分图，通信，外存执行，在线查询，容错等方面的改进，相关系统统称为BigGraph@CUHK（http://www.cse.cuhk.edu.hk/systems/graph/），在SIGMOD, VLDB，IEEE TPDS, WWW，IEEE/ACM TCBB，ICPP等会议和期刊上发表了10多篇相关论文，带领的团队成员包括后来去MIT读博的Yi Lu以及刚刚拿到多伦多大学教职的Qizhen Zhang。加入阿拉巴马大学伯明翰分校后（2016-now），在充分意识到顶点式框架局限性后，严达积极推广任务式框架T-thinker，近10篇相关工作发表在VLDB, ICDE, VLDB Journal, ACM TODS等顶会顶刊上，今年第一个博士学生Guimu Guo毕业并作为助理教授将于秋季加入美国新泽西的Rowan大学。目前严达正积极推广T-thinker框架的实际应用和部署。严达在Foundations and Trends in Databases上有一本涵盖图计算系统领域各个方面的书，并在SIGMOD，VLDB，ICDE，KDD，AAAI，IJCAI等顶会以及ACM TODS, VLDB Journal, IEEE TKDE，IEEE TPDS等顶刊上担任论文评委，在ACM/IEEE TCBB和BMC Bioinformatics担任客座主编，并经常组织BIOKDD workshop和达堡论坛（Dagstuhl Seminar）等学术活动。