III: Small: Enabling Declarative Querying and Analytics over Large Dynamic Information Networks

III：小型：在大型动态信息网络上实现声明式查询和分析

• 批准号: 1319432
• 负责人: Amol Deshpande
• 金额: $ 50万
• 依托单位: University of Maryland, College Park
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2013
• 资助国家: 美国
• 起止时间: 2013-09-01 至 2017-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1319432&HistoricalAwards=false
• 关键词: III; Small; Enabling; Declarative; Querying

In this project, we are building a graph data management system and a suite of tools aimed at supporting real-time, historical, and analytics queries over very large, dynamic, heterogeneous, and noisy information networks. Examples of such information networks include social networks, communication networks, financial transaction networks, citation networks, gene regulatory networks, disease transmission networks, ecological food networks, sensor networks, social contact graphs, and many more. Network data is most naturally represented as a graph, with nodes representing the entities and edges denoting the interactions between them. There is, however, a lack of established data management systems that provide declarative frameworks for querying and analysing such graph-structured data, especially very large volumes of heterogeneous, complex-structured, and rapidly changing data. In this project, we are developing a set of formalisms that include: (a) a declarative query language for graph data, (b) a declarative framework for specifying complex, iterative network analysis tasks like entity resolution, link prediction, etc., and (c) a general-purpose neighborhood-centric distributed programming framework. Our declarative interfaces and the programming framework are based on "Datalog", a well-established database query language, providing the users or the analysts a consistent abstraction of the graph data to specify their queries or tasks. We are designing a suite of techniques, algorithms, and index data structures, to efficiently store large volumes of time-evolving graph data, and to execute queries and analysis tasks over it. We are addressing the challenges in minimizing network communication overhead during distributed computation through designing new partitioning and adaptive replication techniques. We are also developing a compression-based approach to minimize the resources needed for graph processing, and a framework for extrapolating missing historical information to enable querying over incomplete historical traces. Managing and reasoning about graph data is increasingly becoming crucial in many real-world application domains including social media, e-science, disease epidemics, and financial markets, to name a few. The frameworks and tools that we are developing make it easier and more intuitive for domain experts and analysts to process, analyze, and extract insights from large volumes of dynamic time-evolving graph data. Our system enables temporal evolutionary analytics over very large historical traces, and continuous and real-time analytics over highly dynamic graphs, thus enabling a rich class of applications that would not have been possible before. The declarative frameworks and the query language that we are developing have the potential to transform and streamline the highly fragmented research area of graph query processing and analytics. This project provides research opportunities for graduate and undergraduate students, and is aligned with several undergraduate and graduate courses offered by the PI. For further information, see the project web site at: http://www.cs.umd.edu/~amol/GrDB

在这个项目中，我们正在构建一个图形数据管理系统和一套工具，旨在支持非常大的，动态的，异构的和嘈杂的信息网络上的实时，历史和分析查询。这样的信息网络的示例包括社交网络、通信网络、金融交易网络、引用网络、基因调控网络、疾病传播网络、生态食物网络、传感器网络、社交联系图等等。网络数据最自然地表示为图，节点表示实体，边表示它们之间的交互。然而，缺乏已建立的数据管理系统，其提供用于查询和分析这种图形结构化数据的声明性框架，特别是非常大量的异构、复杂结构和快速变化的数据。在这个项目中，我们正在开发一组形式主义，包括：（a）用于图数据的声明性查询语言，（B）用于指定复杂的声明性框架，迭代网络分析任务，如实体解析，链接预测等，以及（c）通用的以邻居为中心的分布式编程框架。我们的声明式接口和编程框架是基于“Datasheet”，一个完善的数据库查询语言，提供用户或分析师的图形数据的一致抽象，以指定他们的查询或任务。我们正在设计一套技术，算法和索引数据结构，以有效地存储大量的随时间变化的图形数据，并执行查询和分析任务，我们正在解决的挑战，在分布式计算过程中，通过设计新的分区和自适应复制技术，最大限度地减少网络通信开销。我们还在开发一种基于压缩的方法，以最大限度地减少图形处理所需的资源，并开发一个框架，用于推断缺失的历史信息，以实现对不完整历史痕迹的查询。管理和推理图数据在许多现实世界的应用领域中变得越来越重要，包括社交媒体，电子科学，疾病流行和金融市场等。我们正在开发的框架和工具使领域专家和分析师能够更轻松，更直观地处理，分析和从大量动态时间演变图数据中提取见解。我们的系统能够对非常大的历史轨迹进行时间演化分析，并对高度动态的图形进行连续和实时分析，从而实现了丰富的应用程序，这在以前是不可能的。我们正在开发的声明式框架和查询语言有可能改变和简化高度分散的图查询处理和分析研究领域。该项目为研究生和本科生提供研究机会，并与PI提供的几门本科和研究生课程保持一致。欲了解更多信息，请访问项目网站：http://www.cs.umd.edu/~amol/GrDB