机器之心专栏 　　

　　

　　严达 （Daniel Yan）| yanda@uab.edu 　　

　　

　　计算机科学系助理教授 | 美国阿拉巴马大学伯明翰分校 　　

　　

　　请随意跳过正文，观看最后的讲座视频，直接了解T-thinker。 　　

　　

　　什么？是不是又一次关于设计类似并行编程框架的炒作？是不是另一种方式统一了各种简单坏街问题(Join、连通分量、单源最短路径、PageRanks)的编程接口(答案是否定的，我们处理的是更高级更多样的计算问题)？这跟我有什么关系？ 　　

　　

　　不要急着走…下面几段我马上告诉你！与以前的并行编程框架不同，T-thinker针对的是计算密集型任务。相反，现有编程框架是针对数据密集型（data-intensive）任务的，在处理是针对计算密集型任务时可能比单机上的串行程序还慢（哪怕你用上 1000 台电脑同时算）！你不相信？我来列举一下证据。 　　

　　

　　这种现象早在10年前就被发现了：西达尔特苏里和谢尔盖瓦西里维茨基在2011年的WWW大会上发表了题为《Counting triangles and the curse of the last reducer》的论文，首创了MapReduce版本的数字三角形算法(根据谷歌的引用，目前已被引用480多次)。 　　

　　

　　然而，一年后，Shumo Chu和James Cheng在他们的ACM TKDD期刊论文《Triangle listing in massive networks》中尖锐地指出， Suri和Sergei Vassilvitskii的MapReduce方法使用1636台计算机整整花费了5.33个点。Clock刚刚完成了一个计算三角形的任务，而Shumo Chu和James Cheng提出的单机外存串行算法，同样的任务只用了0.5分钟！ 　　

　　

　　换句话说，为了使用分布式框架，西达尔特苏里和谢尔盖瓦西里维茨基花费了1636倍的计算资源却得到了10倍的性能减速！无独有偶，弗兰克麦克雪莉(Frank McSherry)等人在他们的HotOS 2015研讨会论文《Scalability! But at what COST?》中尖锐地指出，现有的顶点图计算系统的性能几乎与在笔记本上运行一个简单的串行程序相同。之后Frank McSherry在diss博客(《COST in the land of databases》)(3359 github . com/frankMcSherry/blog/blob/master/posts/2017-09-23 . MD)中进一步不满大数据系统研究(详见图1)… 　　

　　

　　 　　

　　

　　图1:作者1对大数据系统的评论：Frank McSherry博客“数据库领域的成本”。 　　

　　

　　这里性能问题的根源在于，对于一个有N个点的图，数字三角形的复杂度是O(n 1.5)，而一般的数据密集型框架最擅长的是迭代计算，即运行有限次数的迭代轮次(如常数或O(log n))，每轮次的代价与输入(O(n))成线性关系。换句话说，数据密集型框架擅长的算法的总工作量被限制在O(n log n)的量级。 　　

　　

　　这个结论已经被很多人注意到了。比如范等人在PVLDB'13上发表的论文《Making queries tractable on big data with preprocessing》和等人在SIGMOD'14上发表的论文《Scalable big graph processing in MapReduce》，都指出扩展性好的MapReduce程序都是O(n log n)，作者领导的在PVLDB'14上发表的论文《Pregel algorithms for graph connectivity problems with performance guarantees》对Google的Pregel框架下的图计算程序给出了同样的结论。相反，T-thinker框架可以轻松应对NP难的计算问题，并保证计算性能随着CPU内核的增加而显著提升！ 　　

　　

　　如果你还没有被说服继续读下去，而你又恰好是一个从事大数据系统和算法研究的学者(行业内见文末，不要走开！)，那我们就来看看T-thinker的研究在顶级计算机会议和期刊上能有多高产吧！值得注意的是，T-thinker是一个非常新的话题：初步概念发表在作者在PPoPP'19上发表的海报论文《T-Thinker 3360a以任务为中心的分布式Compu框架》中。 　　

te-Intensive Divide-and-Conquer Algorithms》上，并且被计算研究协会（CRA）的计算社区联盟（CCC）评为伟大的新创意之一（https://cra.org/ccc/great-innovative-ideas/t-thinker-a-task-centric-framework-to-revolutionize-big-data-systems-research/，见图 2）。可以看 YouTube 的小伙伴们的可以戳这里看 T-thinker 相关的介绍性短视频: https://www.youtube.com/watch?v=3ub2ACLlg6M （见图 3）。

　　

　　

图 2：T-thinker 被评为 CCC Great Innovative Idea。

　　

　　

图 3：CCC 早期职业学者研讨会上笔者对 T-thinker 的介绍性短视频

　　

从 2020 年开始笔者的研究团队开始根据 T-thinker 框架开发了一系列大数据挖掘系统，均发表在数据库最顶级的会议及期刊上。第一个系统是 G-thinker，用于解决从大图上寻找满足用户定义的条件的子图实例的问题，比如数三角形，找高密度子图（比如对应社交团体）以及子图匹配。G-thinker 可以通过 https://bit.ly/gthinker 访问（见图 4），其开发获得美国科学基金（NSF），南部大数据中枢（South BD Hub）以及微软的 Azure 云平台的资助。发表的相关论文顶会顶刊云集，包括：

　　

G-thinker: A Distributed Framework for Mining Subgraphs in a Big Graph (ICDE’20)Scalable Mining of Maximal Quasi-Cliques: An Algorithm-System Codesign Approach (PVLDB’20)G-thinker: A General Distributed Framework for Finding Qualified Subgraphs in a Big Graph with Load Balancing (VLDB Journal 2022)Parallel Mining of Large Maximal Quasi-Cliques (VLDB Journal, accepted in 2021)Maximal Directed Quasi-Clique Mining (ICDE’22)笔者博士生郭桂木（同济大学硕士）在 G-thinker 研究方面做出了重要贡献，并于今年（2022）获得了美国新泽西州 Rowan 大学长聘轨制助理教授的职位。其他博士在读团队成员也是顶会顶刊论文云集，并正不断着手开发新的基于 T-thinker 框架的数据挖掘系统。

　　

　　

图 4：G-thinker 系统首页。

　　

第二个基于 T-thinker 框架的系统是 PrefixFPM，用于在事务（transaction）数据库上挖掘各种频繁的模式 (pattern)，即被超过一定指定数量事务包含的模式。模式的类型由用户灵活指定，包括 itemset，子树，子图，甚至是子矩阵。发表的相关论文也是顶会顶刊云集，包括：

　　

PrefixFPM: A Parallel Framework for General-Purpose Frequent Pattern Mining (ICDE’20)Parallel Mining of Frequent Subtree Patterns (LSGDA@VLDB’20, invited keynote)PrefixFPM: A Parallel Framework for General-Purpose Mining of Frequent and Closed Patterns (VLDB Journal 2022)Mining Order-Preserving Submatrices Under Data Uncertainty: A Possible-World Approach and Efficient Approximation Methods (ACM TODS, accepted in 2022)频繁模式挖掘的另一个环境设定是考虑一个单独的大事务，比如一张大图或者一个地理空间数据集 (for colocation patterns)。与该环境设定对应的系统笔者的博士生 Lyuheng Yuan（UPenn 硕士）正在如火如荼的开发中，相信不久后就会面世。

　　

第三个基于 T-thinker 框架的系统是 TreeServer，用于构建基于决策树的各种预测模型，包括 deep forest 这样的大模型。相关论文《Distributed Task-Based Training of Tree Models》今年在 ICDE’22 上发表。

　　

值得注意的是，T-thinker 系列系统的研究仅仅刚刚开始，而且笔者研究团队目前还有好多相关系统已经筹划好排着队等待开发！相信还有非常多的研究机会等待大家发掘（行动要快喔）！笔者第一个博士生郭桂木（大弟子）在 IEEE BigData 2020 对这个方向有个教程报告（tutorial），您有兴趣的话欢迎访问 https://www.youtube.com/watch?v=uq4CndPj6pY 观看。希望到这里我已经说服你来了解下 T-thinker 到底是什么，以及我们 T-thinker 的相关工作了。

　　

什么？你是工业界的且对发系统论文不感兴趣？别走开啊，注意我们的题目：T-thinker 是继 MapReduce, Apache Spark 之后的下一代大数据并行编程框架！T-thinker 克服了现在数据密集型系统对计算密集型任务的执行低效问题，但是它同样可以高效支持数据密集型任务！发现了吗？T-thinker 可能是取代 Spark 等大数据编程框架的下一代编程模型！注意到没有，现在大家都用 Spark 已经没什么人用过时的 MapReduce 了…

　　

想不想成为自己公司第一个启动 T-thinker 编程框架项目或者 T-thinker 云平台支持的负责人？还等什么，赶快听一下下面为时一小时干货满满的讲座，详细了解下 T-thinker 的技术概念吧！

　　

视频链接：https://www.bilibili.com/video/BV1kY411K7eh?spm_id_from=333.999.0.0