CAREER: Querying Evolving Graphs

职业：查询演化图

• 批准号: 1916505
• 负责人: Julia Stoyanovich
• 金额: $ 49.78万
• 依托单位: New York University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2018
• 资助国家: 美国
• 起止时间: 2018-09-01 至 2024-02-29
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1916505&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.

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

项目成果

Most Expected Winner: An Interpretation of Winners over Uncertain Voter Preferences

最受期待的获胜者：对不确定选民偏好的获胜者的解读

• 发表时间: 2023
• 期刊: Proceedings of the '23 International Conference on the Management of Data (ACM SIGMOD 2023
• 作者: Haoyue Ping;Julia Stoyanovich
• 通讯作者: Julia Stoyanovich

Data distribution debugging in machine learning pipelines

• DOI: 10.1007/s00778-021-00726-w
• 发表时间: 2022-01
• 期刊: The VLDB Journal
• 作者: Stefan Grafberger;Paul Groth;Julia Stoyanovich;Sebastian Schelter

Generating Evolving Property Graphs with Attribute-Aware Preferential Attachment

使用属性感知优先附件生成演化属性图

• DOI: 10.1145/3209950.3209954
• 发表时间: 2017
• 期刊: DBTest'18 Proceedings of the Workshop on Testing Database Systems
• 作者: Aghasadeghi, Amir;Stoyanovich, Julia
• 通讯作者: Stoyanovich, Julia

Causal Intersectionality and Fair Ranking

因果交叉性和公平排名

• 发表时间: 2021
• 期刊: 2nd Symposium on Foundations of Responsible Computing (FORC
• 作者: Yang, Ke;Loftus, Joshua R.;Stoyanovich, Julia
• 通讯作者: Stoyanovich, Julia

Counterfactuals for the Future

未来的反事实

• 发表时间: 2023
• 期刊: Proceedings of the AAAI Conference on Artificial Intelligence
• 作者: Bynum, Lucius;Loftus, Joshua;Stoyanovich, Julia
• 通讯作者: Stoyanovich, Julia