EPSRC logo

Details of Grant 

EPSRC Reference: EP/J015377/1
Title: Querying Graph Structured Data: Principles and Techniques
Principal Investigator: Libkin, Professor L
Other Investigators:
Fan, Professor W
Researcher Co-Investigators:
Project Partners:
Department: Sch of Informatics
Organisation: University of Edinburgh
Scheme: Standard Research
Starts: 01 November 2012 Ends: 31 October 2016 Value (£): 637,076
EPSRC Research Topic Classifications:
Fundamentals of Computing Information & Knowledge Mgmt
EPSRC Industrial Sector Classifications:
Information Technologies
Related Grants:
Panel History:
Panel DatePanel NameOutcome
01 Feb 2012 EPSRC ICT Responsive Mode - Feb 2012 Announced
Summary on Grant Application Form
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.

Key Findings
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Potential use in non-academic contexts
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Description This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Date Materialised
Sectors submitted by the Researcher
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Project URL:  
Further Information:  
Organisation Website: http://www.ed.ac.uk