CAREER: Querying Evolving Graphs

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

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.