This project has supported the PI and a number of PhD students to investigate novel parallel and distributed programming models and systems for accelerating compute-intensive analytics of graph data and matrix/tensor data. Through the investigation conducted in this project, a suite of new systems have been designed and implemented, particularly:

(1) G-thinker (https://bit.ly/gthinker), a distributed system for mining subgraphs that satisfy user-defined requirements (e.g., subgraph matching, quasi-cliques);

(2) PrefixFPM (https://github.com/wenwenQu/PrefixFPM), a general-purpose parallel programming framework for mining all kinds of frequent or closed patterns (subsequence, subtrees, subgraphs and submatrices).

(3) TreeServer (https://github.com/yanlab19870714/TreeServer), a system to train decision tree ensemble models, including deep forest which often contains a large number of trees.

The systems developed are all based on the T-thinker programming paradigm (i.e., think like a task, where "T" means "task") proposed by the PI in a poster in PPoPP 2019, and advertised by CCC as a great innovative idea at https://cra.org/ccc/great-innovative-ideas/t-thinker-a-task-centric-framework-to-revolutionize-big-data-systems-research/ 

Put simply, the idea of the T-thinker programming paradigm is that for compute-intensive problems, we can divide the problem space recursively until a sufficiently small unit is obtained, which we call a task. A worker machine can then obtain the subset of data needed for the task (linear communication cost), and compute it afterwards (often high time complexity). Since computation is the bottleneck, data moving cost can mostly be overlapped with the concurrent computation so that all CPU cores can be fully utilized. This is in contrast to existing cyberinfrastructure that targets data-intensive problems, which when used to solve compute-intensive problems, the performance is comparable to a single-threaded program as indicated by Frank McSherry https://github.com/frankmcsherry/blog/blob/master/posts/2017-09-23.md

Besides, tools for matrix and tensor factorization have also been investigated and developed. A number of publications in high impact venues have been published including VLDB, ICDE, VLDB Journal, ACM TODS, KDD, ICDM, etc.  The results have been disseminated by paper presentations in the respective conferences, a tutorial in IEEE BigData 2020, an invited keynote talk at the LSGDA workshop held in conjunction with VLDB 2020, Dagstuhl Seminars (19491, 19051, 22031), and invited talks at various universities.

Regarding the broader impacts, while data-intensive cyberinfrastructure is in wide need and sees the biggest investment, there are applications where the time complexity of computation is very high, and the availability of only data-intensive cyberinfrastructure causes misuse and hence huge waste of resources and energy. System paradigms highly-efficient for those costly computations are in urgent need to alleviate this problem, but they require non-trivial efforts to design and develop, and they were not given enough attention. During the project period, the PI's team has been advocating the design of compute-intensive programming paradigms and systems, and T-thinker is a viable paradigm along this line. The research outcomes have gained a lot of attention and a productive research team has been built around the T-thinker research. Besides a number of PhD students (including one who defended and found a tenure-track faculty job), the project also trained Master's students at UAB advised by Directed Readings course, high-school summer interns, and visiting scholars. The trainees will contribute to the next-generation Big Data workforce proficient in systems and HPC research, and parallel and distributed algorithms.

Last Modified: 06/11/2022
Modified by: Da Yan