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

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

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