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 facilitate
understanding 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.

The following will benefit from our research:

- Private sector, such as vendors for graph databases (Yahoo!, Amazon, etc.) and providers of social networks (LinkedIn, Twitter, FaceBook, etc.).

- Public sector, such as organisations involved in crime detection, intelligence analysis, and transportation networks;

- The wider public, such as users of semantic Web and social networks; and

- Research community across several disciplines such as knowledge discovery, biology, cheminformatics, cloud computing, semantics Web and social networks.

They will benefit in the following ways:

(a) The project will provide guidance for designing new graph query languages.

(b) Our query evaluation algorithmic toolbox will help developers of graph databases better support querying graph data.

(c) Our tools will provide users of graph data (e.g., social networks) with more effective and efficient data access.

To deliver the impact, we shall do the following:

- continue ongoing and establish new industrial collaborations; provide packaged solutions at various stages for our industrial collaborators to evaluate, to ensure that our tools and techniques are properly tested to guarantee their practicality;

- continue active interaction with leading researchers on graph databases, and publish results of our research in top venues to ensure maximum visibility; and

- deliver seminars, public lectures, and enhance existing and create new teaching modules based on the outcomes of this project.