电脑之心时评
严达 （Daniel Yan）| yanda@uab.edu
排序机科学系现职副教授 | 美国康涅狄格理工学院布里斯托尔附属小学
[热烈欢迎即时埃唐佩县文本看最后的专题讲座音频间接介绍 T-thinker]。
甚么？是不是又是两个有关结构设计略有不同的博戈达程式结构设计架构的炒？呢又是把各种单纯烂大街难题（join, connected components, single-source shortest paths, PageRanks）标准化呵呵程式结构设计USB（标准答案是不，我们处置更高阶多样化的排序难题）？那个与我有甚么亲密关系？
喽着返回… 接下去两段立刻说你！与过往的博戈达程式结构设计架构不同，T-thinker 是特别针对排序专门化（compute-intensive）各项任务的。恰好相反，原有程式结构设计架构是特别针对统计数据专门化（data-intensive）各项任务的，在处置是特别针对排序专门化各项任务时可能比FPS上的以太网流程还慢（即便你用上 1000 台笔记本电脑同时算）！你不坚信？我来列出呵呵确凿证据。
那个现像早在 10 天前就没人发现了：Siddharth Suri 和 Sergei Vassilvitskii 在 2011 年的 WWW 全会上刊登专文《Counting triangles and the curse of the last reducer》的学术论文, 开拓性地明确提出了数正方形演算法的 MapReduce 版（根据Google提及，目前高引达 480 数次）。
不过两年以后 Shumo Chu 和 James Cheng 在他们 ACM TKDD 学术学术论文《Triangle listing in massive networks》中凌厉地表示: Siddharth Suri 和 Sergei Vassilvitskii 的 MapReduce 方式采用 1636 台笔记本电脑耗费了足足 5.33 两分钟才顺利完成两个数正方形的各项任务，而 Shumo Chu 和 James Cheng 明确提出的FPSXC610PA以太网演算法在反之亦然的各项任务上实际上耗费 0.5 两分钟！
换言之，为了采用分布式系统架构，Siddharth Suri 和 Sergei Vassilvitskii 耗费了 1636 倍的排序资源却获得了 10 倍的性能降速！无独有偶，Frank McSherry 等人在他们 HotOS 2015 研讨会学术论文《Scalability! But at what COST?》中凌厉地表示，原有的顶点式图排序系统其性能和在笔记本上跑两个单纯的以太网流程其实差不多。这之后，Frank McSherry 更是在他专文《COST in the land of databases》的部落格(https://github.com/frankmcsherry/blog/blob/master/posts/2017-09-23.md) 进一步 diss 了大统计数据系统研究（具体见图 1）…
图 1：Frank McSherry 部落格 “COST in the Land of Databases” 对大统计数据系统的相关评论。
这里性能难题的根源在于，对于两个含有 n 个点的图，其数正方形的复杂度是 O(n^1.5)，而一般统计数据专门化架构最擅长的是迭代（iterative）排序，即运行有限的迭代轮数（比如常数或者 O(log n)），而且每轮的代价和输入呈线性亲密关系（即 O(n)）。换言之，统计数据专门化架构擅长的演算法的总工作量仅限于 O(n log n)的量级。
该结论被很多人已经注意到，例如樊文飞等在 PVLDB’13 上刊登的学术论文《Making queries tractable on big data with preprocessing》以及 Lu Qin 等在 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 是两个非常新的 topic：初步的概念刊登在笔者等在 PPoPP’19 上的海报（poster）学术论文《T-thinker: A Task-Centric Distributed Framework For Compute-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 了…
