CAREER: Querying Evolving Graphs

职业：查询演化图

• 批准号: 1750179
• 负责人: Julia Stoyanovich
• 金额: $ 54.97万
• 依托单位: Drexel University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2018
• 资助国家: 美国
• 起止时间: 2018-03-01 至 2019-03-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1750179&HistoricalAwards=false
• 关键词: CAREER; Querying; Evolving; Graphs

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.

图表用于代表众多现象，包括网络，社交网络，生物途径，运输网络和语义知识库。关于图形的许多有趣而重要的问题涉及其演变，而不是其静态状态：哪些网页显示出越来越多的流行趋势？社交网络中如何影响？在白天和整个星期内，如何利用运输选择和城市变化的乘车成本？知识如何发展？将这些问题提出为程序目前超出了大多数数据科学家的技能。执行此类程序提出了巨大的效率挑战，尤其是对于数十亿个边缘和非平凡进化率的图表。 如今，许多研究和工程工作都用于开发复杂的图形分析及其有效的实现，无论是独立的还是数据处理平台的范围。但是，仍然缺乏对不断发展的图表进行查询和分析的系统支持。由于不断发展的图形分析所固有的可伸缩性挑战，以及考虑可用性和易于传播的考虑，因此迫切需要这种支持。该项目将通过建立有效的建模和有效分析的基本原理来填补这一空白，并通过在一个名为Portal的开源平台中为使用社区提供结果。该项目将基于时间数据管理中的艺术状态，从而使这些原理和技术在数十年的研究和实践中开发出来，以浏览该图表的数十年来浏览图形应用程序。该项目将开发：（1）用于发展图的数据模型和表达性组成代数； （2）在分布式数据 - 平行框架的范围内，有效地实现了数据结构和代数操作，以及任何必要的代数原始图和物理表示 /访问方法； （3）一种声明的查询语言，支持复杂的图形分析任务的简洁规范，以及生成有效查询执行计划的查询优化器； （4）基于实际和合成数据集和分析任务的可用性和效率的原则评估方法。 该项目将通过为不断发展的图形数据提供新颖的表示，分析和基准方法来影响数据管理的研究和实践。 该项目的结果将有助于将复杂的图形分析纳入较大的应用程序，并可以扩展到现代量。该门户网站框架将支持与社交网络分析，知识管理和网络流量分析中不断发展的图表合作的计算科学家。这项工作的一组重要用例将来自社会良好应用程序的数据科学，包括城市无家可归和对城市的运输利用和成本分析。有关更多信息，请参见项目网页：portaldb.github.io。该奖项反映了NSF的法定任务，并被认为是值得通过基金会的知识分子优点和更广泛影响的审查标准通过评估来支持的。