CRII: OAC: Scalable Cyberinfrastructure for Big Graph and Matrix/Tensor Analytics

CRII：OAC：用于大图和矩阵/张量分析的可扩展网络基础设施

• 批准号: 1755464
• 负责人: Da Yan
• 金额: $ 17.09万
• 依托单位: University of Alabama at Birmingham
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2018
• 资助国家: 美国
• 起止时间: 2018-06-01 至 2022-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1755464&HistoricalAwards=false
• 关键词: CRII; OAC; Scalable; Cyberinfrastructure; Big

The existing distributed graph and matrix analytics frameworks are designed with data-intensive workloads in mind, rendering them inefficient for compute-intensive applications such as graph mining and scientific computing. The goal of this project is to develop novel big data frameworks for two compute-intensive tasks, graph mining and matrix/tensor computations, respectively. The two frameworks advance the field of big data analytics by motivating future systems for compute-intensive analytics, and promoting their application in various scientific areas to improve research productivity. The two systems will be available for public use, and can serve several cross-disciplinary projects in computer forensics, computational physics, and bioinformatics. The project includes mentoring graduate students and training K-12 students through summer internships, as well as related new course materials and outreach activities to help the public learn big data technologies. Thus, the project aligns with the NSF's mission to promote the progress of science and to advance the national health and prosperity.The graph mining system and the matrix/tensor platform share the design of (i) a tailor-made storage subsystem providing efficient and flexible data access, and (ii) a computation subsystem with fine-grained task control for data-reuse-aware task assignment and load balancing. The graph mining system, called G-thinker, aims to facilitate the writing of distributed programs which mine from a big graph those subgraphs that satisfy certain requirements. Such mining problems are useful in many applications like community detection and subgraph matching. These problems usually have a high computational complexity, and existing serial algorithms tackle these problems by backtracking in a duplication-free vertex-set numeration tree, which recursively partitions the search space. G-thinker adopts an intuitive programming interface that minimizes the effort of adapting an existing serial subgraph mining algorithm for distributed execution. The subgraphs to mine are spawned from individual vertices and they grow their frontiers as needed, and memory overflow is avoided by spilling subgraphs to disks when needed. In each machine, vertices and edges shared by multiple subgraphs need only be transmitted and cached once, which minimizes communication (and hence data waiting) so that CPU cores are better utilized. To address the load-balancing problem of power-law graphs, G-thinker explores recursive decomposition and work stealing to allow idle machines to steal subgraphs for mining from heavily-loaded machines. The project also explores a distributed matrix/tensor storage and computing framework, where matrix/tensor partitions are stored in multiple replicas using different storage schemes to efficiently support all kinds of submatrix access operations. This flexible storage scheme offers the upper-layer computations much more opportunities for fine-grained optimizations, including smarter task scheduling and in-situ updates. The use of this framework is exemplified by matrix multiplication and LU factorization. Both of the proposed frameworks can help build a cyberinfrastructure for collaborations with scientists in science, medicine, and industry.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.

现有的分布式图和矩阵分析框架是考虑到数据密集型工作负载的设计，使它们无效地计算诸如图形挖掘和科学计算的计算应用程序效率。该项目的目的是为两个计算密集型任务，图形挖掘和矩阵/张量计算开发新的大数据框架。这两个框架通过激励未来的计算密集分析系统，并促进其在各个科学领域的应用以提高研究生产率，从而推动了大数据分析的领域。这两个系统将用于公共使用，并可以在计算机取证，计算物理学和生物信息学中为几个跨学科项目提供服务。该项目包括指导研究生和通过暑期实习培训K-12学生，以及相关的新课程材料和外展活动，以帮助公众学习大数据技术。因此，该项目符合NSF促进科学进步并提高民族健康和繁荣的使命。图形挖掘系统和矩阵/张量平台共享（i）（i）量身定制的存储子系统的设计，可提供有效且灵活的数据访问，以及（ii）计算子系统，具有良好的数据控制数据控制数据控制的计算子系统。 Graph挖掘系统（称为G-THENINGER）旨在促进分布式程序的编写，这些程序从大图中挖掘出满足某些要求的子图。这种采矿问题在许多应用程序中很有用，例如社区检测和子图匹配。这些问题通常具有较高的计算复杂性，现有的串行算法通过在无重复的顶点计算树中回溯来解决这些问题，该基因将搜索空间递归分区。 G-THENINGER采用直观的编程接口，该接口最大程度地减少了为分布式执行的现有串行子图挖掘算法调整现有的串行子图挖掘算法的努力。我的子图是从各个顶点产生的，它们会根据需要生长其前沿，并在需要时通过将子图洒到磁盘上来避免记忆溢出。在每台计算机中，只需传输和缓存一次由多个子图共享的顶点和边缘一次，这可以最大程度地减少通信（以及数据等待），以便更好地利用CPU内核。为了解决幂律图的负载平衡问题，G-Thinker探索了递归分解和窃取工作，以允许空闲的机器窃取子图从重装机器中挖掘。该项目还探讨了分布式矩阵/张量存储和计算框架，其中使用不同的存储方案将矩阵/张量分区存储在多个副本中，以有效地支持各种subpatrix访问操作。这种灵活的存储方案为高层计算提供了更多的机会，以进行细粒度的优化，包括更智能的任务调度和现场更新。矩阵乘法和LU分解来说明了此框架的使用。拟议的两个框架都可以帮助建立与科学，医学和行业科学家合作的网络基础设施。该奖项反映了NSF的法定任务，并被认为是值得通过基金会的知识分子和更广泛影响的评估审查标准来通过评估来支持的。

项目成果

The Future is Big Graphs! A Community View on Graph Processing Systems

未来是大图！

• 发表时间: 2021
• 期刊: Communications of the ACM
• 影响因子: 22.7
• 作者: Sakr, Sherif;Bonifati, Angela;Voigt, Hannes;Iosup, Alexandru;Ammar, Khaled;Angles, Renzo;Aref, Walid G.;Arenas, Marcelo;Besta, Maciej;Boncz, Peter A.
• 通讯作者: Boncz, Peter A.

Parallel mining of large maximal quasi-cliques

• DOI: 10.1007/s00778-021-00712-2
• 发表时间: 2021-11
• 期刊: The VLDB Journal
• 作者: J. Khalil;Da Yan;Guimu Guo;Lyuheng Yuan

Accurate Tensor Decomposition with Simultaneous Rank Approximation for Surveillance Videos

• DOI: 10.1109/ieeeconf51394.2020.9443285
• 发表时间: 2020-01-01
• 期刊: 2020 54TH ASILOMAR CONFERENCE ON SIGNALS, SYSTEMS, AND COMPUTERS
• 作者: Karim，Ramin Goudarzi;Guo，Guimu;Navasca，Carmeliza
• 通讯作者: Navasca，Carmeliza

G-thinker: A Distributed Framework for Mining Subgraphs in a Big Graph

• DOI: 10.1109/icde48307.2020.00122
• 发表时间: 2020-04
• 期刊: 2020 IEEE 36th International Conference on Data Engineering (ICDE)
• 作者: Da Yan;Guimu Guo;Md Mashiur Rahman Chowdhury;M. Tamer Özsu;Wei-Shinn Ku;John C.S. Lui

Parallel Mining of Frequent Subtree Patterns

• DOI: 10.1007/978-3-030-61133-0_2
• 发表时间: 2020-09
• 作者: Wenwen Qu;Da Yan;Guimu Guo;Xiaoling Wang;Lei Zou;Yang Zhou