High Performance Graph Algorithms and Data Structures

高性能图算法和数据结构

• 批准号: RGPIN-2022-03207
• 负责人: Peng, Yang(Richard)
• 金额: $ 4.39万
• 依托单位: University of Waterloo
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2022
• 资助国家: 加拿大
• 起止时间: 2022-01-01 至 2023-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=750224
• 关键词: Performance; Graph; Algorithms; Data; Structures

Computation on large scale data is closely connected with tools such as linear system solvers, convex optimization, and systems for storing dynamically changing networks. These tools are integrated in many high-level programming languages such as MATLAB, Python, and Julia, which are in turn widely used in machine learning, statistics, and scientific computing. The long term goal of this research program is to develop a new generation of algorithmic primitives suitable for inputs several order of magnitudes larger than what we currently process. Specifically, we hope to develop highly efficient and theoretically well-founded algorithms for processing graphs and sparse matrices in both static and dynamic settings. It builds upon recent breakthroughs in algorithms for fundamental graph problems, namely almost nearly-linear time solvers for graph structured linear systems, faster algorithms for network flows, and dynamic maintenance of higher connectivity values. The shorter term (5 year) objectives are: * Investigate and classify structured sparse linear systems, especially ones related to graphs, with the goal of refining and improving numerical primitives for manipulating them. * Develop almost linear time algorithms for solving wide ranges of graph optimization problems to high accuracy. * Better understand data structures for maintaining solutions of optimization problems on dynamically changing graphs. The proposed work revolves around two of the most widely used numerical primitives: iteration and elimination. Generalizing them to wide classes of computational problems will lead to a host of new algorithmic primitives suitable for the large-scale graph and sparse matrices. Such primitives are the silent workhorse of much of large-scale computation today, including the search engines that power the modern internet. Improvements on them have led to, and will continue to lead to, accelerated drug design, better social network analytics, more accurate recommendation of products to users, and more. This research program includes the supervision of both undergraduate and graduate students, the development of courses that connect numerical and combinatorial algorithms, as well as the organization of algorithmic problem solving outreach activities. Students involved will gain knowledge in the latest development of algorithms, develop independent research skills, and gain supervision/organization experiences through involvements in outreach activities. Such skills are highly sought after in both industry and academia: for example, the social media company Facebook has plans of hiring 35000 employees in its Bay Area facility, the web-based delivery company Amazon expanded by about 50% over the past year, the Computer Research Association reported that the size of CS programs tripled on average between 2006 and 2017, and major research universities hired over 70 faculties in theoretical computer science during the 2021-2022 cycle.

大规模数据的计算与线性系统求解器、凸优化和存储动态变化网络的系统等工具密切相关。这些工具集成在许多高级编程语言中，如MATLAB，Python和Julia，这些语言又广泛用于机器学习，统计和科学计算。这项研究计划的长期目标是开发新一代的算法原语，适用于比我们目前处理的输入大几个数量级的输入。具体来说，我们希望开发高效和理论上有充分依据的算法，用于处理静态和动态设置中的图形和稀疏矩阵。它建立在基本图问题算法的最新突破之上，即图结构线性系统的几乎线性时间求解器，网络流的更快算法，以及更高连通性值的动态维护。短期（5年）目标是：* 调查和分类结构化稀疏线性系统，特别是与图形相关的系统，目标是改进和改进用于操作它们的数值原语。* 开发几乎线性时间算法，以高精度解决各种图形优化问题。* 更好地理解数据结构，以便在动态变化的图形上维护优化问题的解决方案。拟议的工作围绕两个最广泛使用的数值原语：迭代和消除。将它们推广到广泛的计算问题，将导致一系列新的算法原语，适用于大规模的图形和稀疏矩阵。这些原语是当今许多大规模计算的无声主力，包括为现代互联网提供动力的搜索引擎。对它们的改进已经导致并将继续导致加速药物设计，更好的社交网络分析，更准确地向用户推荐产品等等。 该研究项目包括对本科生和研究生的监督、开发连接数值和组合算法的课程，以及组织算法问题解决外展活动。参与的学生将获得算法最新发展的知识，发展独立的研究技能，并通过参与外展活动获得监督/组织经验。这些技能在工业界和学术界都受到高度追捧：例如，社交媒体公司Facebook计划在其湾区工厂雇用35000名员工，基于网络的交付公司亚马逊在过去一年中扩大了约50%，计算机研究协会报告称，CS程序的规模在2006年至2017年期间平均增加了两倍，主要研究型大学在2021-2022年周期内聘请了70多名理论计算机科学教师。