Collaborative Research: PPoSS: Planning: Extreme-scale Sparse Data Analytics

图形数据结构用于存储和操作关系数据。张量是二维矩阵表示的高阶推广。图形和张量都用于探索性和自动化数据分析。应用领域包括网络安全、复杂系统分析和个性化医疗。对于这些领域中的典型数据分析任务，存在无数已知的算法。例如，图中的社区识别问题，指的是自动识别图中连接良好的顶点组，有几十种算法。与矩阵中的奇异值分解类似，存在几种具有不同用例的张量分解。图形算法和张量分解都使用受矩阵计算启发的计算机存储格式。该项目专注于数据分析用例，这些用例产生大规模的图形和张量，需要并行和分布式处理。该项目的创新之处在于确定和开发了跨越多个图计算和张量分解的统一并行算法设计原则。在规划阶段，几个重点研究任务将探索八个统一的主题。该项目旨在开发一个端到端流数据分析系统的基础，其性能可与当前高端工作站和超级计算机上高度调整的静态图形分析基准相媲美。研究人员的多学科专业知识涵盖高性能计算、理论和算法、计算机体系结构以及编程语言和编译器。交叉研究的目标包括编排节点内和节点间通信的通用原则、利用分层并行的多种方法、局部性增强策略和自动性能调整。规划阶段的软件构件可以构成新的数据分析基准的基础。研究人员将把研究成果纳入他们教授的课程中。在规划阶段聘请国家实验室和该行业的专家将有助于巩固未来的大规模努力。调查人员将利用并促进现有的机构项目，扩大对计算研究的参与。这一奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

The graph data structure is used for storing and manipulating relational data. Tensors are a higher-order generalization of the two-dimensional matrix representation. Both graphs and tensors are used in exploratory and automated data analysis. Applications areas include cybersecurity, complex system analysis, and personalized healthcare. There exist a myriad of known algorithms for typical data analysis tasks in these areas. For instance, the problem of community identification in graphs, referring to automatically identifying well-connected groups of vertices in graphs, has dozens of algorithms. Analogous to the singular value decomposition in matrices, several tensor factorizations exist with diverse use-cases. Both graph algorithms and tensor factorizations use computer storage formats inspired by matrix computations. This project focuses on data analysis use-cases that result in large-scale graphs and tensors, necessitating parallel and distributed processing. The project's novelties are in identifying and developing unifying parallel algorithm design principles that span multiple graph computations and tensor factorizations. In the planning stage, several focused research tasks will explore eight unifying themes.The project aims to develop the foundations for an end-to-end streaming data analytics system with performance comparable to highly tuned static graph analysis benchmarks on current high-end workstations and supercomputers. The investigators' multi-disciplinary expertise span high-performance computing, theory and algorithms, computer architecture, and programming languages and compilers. The cross-cutting research aims include generalizable principles to orchestrate intra- and inter-node communication, multiple approaches for exploiting hierarchical parallelism, locality-enhancing strategies, and automatic performance tuning. The software artifacts from the planning stage could form the basis for new data analytic benchmarks. The investigators will incorporate research findings into the courses they teach. Engaging experts from the national laboratories and the industry in the planning stage will help solidify future large-scale efforts. The investigators will leverage and contribute to existing institutional programs that broaden participation in computing research.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.