Querying Graph Structured Data: Principles and Techniques

点击翻译按钮获取中文摘要

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.