CAREER: Querying Evolving Graphs

图被用来表示过多的现象，包括Web、社会网络、生物路径、交通网络和语义知识库。关于图的许多有趣和重要的问题都与它们的演化有关，而不是它们的静态：哪些Web页面显示出越来越受欢迎的趋势？影响力是如何在社交网络中传播的？一座城市的交通选择利用率和出行成本在白天和整个星期是如何变化的？知识是如何进化的？将这些问题表述为程序，目前超出了大多数数据科学家的技能。执行这样的程序带来了巨大的效率挑战，特别是对于具有数十亿条边的图，并且具有不平凡的进化速度。今天，许多研究和工程工作都投入到开发复杂的图形分析及其高效实现上，包括独立的和数据处理平台范围内的。然而，对演化图的查询和分析仍然缺乏系统的支持。由于不断发展的图表分析所固有的可伸缩性挑战，以及对可用性和易传播性的考虑，迫切需要这种支持。这个项目将通过建立有效建模和有效分析演变图的基本原则来填补这一空白，并通过将结果提供给开放源代码平台Portal.该项目将建立在时态数据管理的最新技术之上，使在该领域数十年的研究和实践中开发的原则和技术可用于演变图应用程序。该项目将开发：(1)演化图形和富于表现力的组成代数的数据模型；(2)在分布式数据并行框架范围内有效实施数据结构和代数运算，以及任何必要的代数原语和物理表示/访问方法；(3)支持复杂图形分析任务的简明说明的陈述性查询语言，以及生成高效查询执行计划的查询优化器；(4)基于真实和合成数据集和分析任务的可用性和效率的原则性评价方法。该项目将通过为不断发展的图表数据提供新的表示、分析和基准方法来影响数据管理的研究和实践。该项目的成果将有助于将复杂的不断发展的图表分析纳入更大的应用程序，并将能够扩大到现代规模。门户框架将支持在社交网络分析、知识管理和网络流量分析中使用演变图的计算和数据科学家。这项工作的一组突出用例将来自社会公益应用的数据科学，包括城市无家可归者和城市交通利用和成本分析。该奖项反映了NSF的法定使命，通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为是值得支持的。

Graphs are used to represent a plethora of phenomena, including the Web, social networks, biological pathways, transportation networks, and semantic knowledge bases. Many interesting and important questions about graphs concern their evolution rather than their static state: Which Web pages are showing an increasing popularity trend? How does influence propagate in social networks? How do the utilization of transportation options and the cost of ridership in a city change during the day and throughout the week? How does knowledge evolve? Formulating these questions as programs is currently beyond the skills of most data scientists. Executing such programs poses tremendous efficiency challenges, especially for graphs with billions of edges, and with non-trivial evolution rates. Much research and engineering effort today goes into developing sophisticated graph analytics and their efficient implementations, both stand-alone and in scope of data processing platforms. Yet, systematic support for querying and analysis of evolving graphs is still lacking. This support is urgently needed, due both to the scalability challenges inherent in evolving graph analysis, and to considerations of usability and ease of dissemination. This project will fill this gap by establishing the fundamental principles of effective modeling and efficient analysis of evolving graphs, and by making results available to the community of use in an open-source platform called Portal.This project will build on the state of the art in temporal data management, making the principles and techniques that were developed over decades of research and practice in that domain available to evolving graph applications. The project will develop: (1) a data model for evolving graphs and an expressive compositional algebra; (2) an efficient implementation of the data structures and of the algebraic operations, together with any necessary algebraic primitives and physical representations / access methods, in scope of a distributed data-parallel framework; (3) a declarative query language that supports concise specification of sophisticated graph analysis tasks, and a query optimizer that generates efficient query execution plans; (4) a principled evaluation methodology of usability and efficiency, based on real and synthetic datasets and analysis tasks. This project will impact research and practice in data management, by contributing novel representation, analysis and benchmarking methods for evolving graph data. Results of this project will help incorporate sophisticated evolving graph analysis into larger applications, and will enable scaling up to modern volumes. The Portal framework will support computational and data scientists who work with evolving graphs in social network analysis, knowledge management and network traffic analysis. A prominent set of use cases for this work will come from data science for social-good applications, including urban homelessness and analysis of transportation utilization and cost in cities. For further information see the project web page: portaldb.github.io.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.