Querying Graph Structured Data: Principles and Techniques

信息处理中最具挑战性的问题之一是处理大量信息(EPSRC在其优先主题“迈向智能信息基础设施”中提到“数据泛滥”和“从信息中理解”是关键问题)。如今，这些海量的信息往往与新的应用程序相关联。例如，LinkedIn、Facebook等社交网络的流行导致它们积累了大量数据。语义网的努力也产生了大量的数据，因为它试图促进对Web数据的理解。这些应用程序中的许多应用程序都有一个共同的特点：底层数据模型由图描述，在查询这种图结构的数据时，图的拓扑与数据本身一样重要。图形数据出现在许多其他应用中，包括情报分析和犯罪侦查、生物学、化学信息学、知识发现和网络流量。同时，图形数据的基本方面还没有得到充分的研究。在共享相同的高级模型的同时，图形数据的应用在很大程度上是相互独立的，产生了独立但相关的数据处理工具集。该项目的主要目标是开发图形数据查询的基本原理和技术，专注于查询语言设计，查询处理任务的算法工具，从超大型图形数据库中快速提供准确或近似的答案，并在原型中实现算法工具箱，供我们的工业合作伙伴使用。主要挑战在于在查询中结合数据和拓扑，图形查询的内在复杂性，以及图形数据的动态和分布式性质。该项目将被分成三个部分。第一部分将集中讨论用于处理数据和拓扑的查询语言设计，以及用于处理超大数据图的查询应答的不同语义。第二个将提供一个算法工具箱，用于查询评估技术、查询处理模式的所有可能组合(批处理与增量)、数据的局部性(单一站点与分布式)以及查询答案的类型(精确与近似)。第三个部分涉及原型的实现，我们将在该原型上测试我们的设计决策和算法。

One of the most challenging problems in information processing is handling large amounts of information (EPSRC, in its priority theme `Towards an intelligent information infrastructure' refers to 'deluge of data' and delivering `understanding from information' as the key problems). Very often nowadays, these vast amounts of information are associated with new applications. For instance, the popularity of social networks such as LinkedIn, Facebook, and others, results in large amounts of data they accumulate. The Semantic Web effort generates high volumes of data too, as it attempts to facilitateunderstanding of Web data. Many of these applications have one feature in common: the underlying data model is described by a graph, and in querying such graph-structured data, the topology of the graph is as important as the data itself. Graph data arises in a multitude of other applications, including intelligence analysis and crime detection, biology, cheminformatics, knowledge discovery, and network traffic.At the same time, foundational aspects of graph data have not yet been adequately studied. While sharing the same high-level model, applications of graph data are developing largely independently of each other, producing separate - but related - sets of data processing tools.The main goal of this project is to develop principles and techniques underlying querying of graph data, concentrating on query language design, algorithmic tools for query processing tasks, delivering exact or approximate answers fast from extremely large graph databases, and implementing the algorithmic toolbox in a prototype to be used by our industrial partners.The main challenges lie in combining data and topology in querying, in the inherent complexity of graph queries, and in the dynamic and distributed nature of graph data. The project will be split into three components. The first will concentrate on query language design for handling data and topology, and on different semantics of query answering for dealing with extremely large data graphs. The second will provide an algorithmic toolbox for query evaluation techniques, for all possible combinations of the query processing mode (batch vs incremental), for the locality of data (single-site vs distributed), and for the type of query answers (exact vs approximate). The third component concerns with the implementation of a prototype on which we shall test our design decisions and algorithms.