ERC Advanced Grant

Resource Bounded Graph Query Answering

The ERC project investigates querying big graphs with bounded resources. The problem is challenging: real-life graphs are typically big, with billions of vertices and trillions of edges; and graph computations are expensive, even intractable. Add to these that we often have constrained resources, such as available time and computing facilities. It demands a departure from the traditional query evaluation techniques and even from the classical computational complexity theory. Indeed, a linear scan of 1PB of data takes days, no longer a tractable query.

The project is to tackle these challenges, from fundamental problems to practical techniques. We will propose graph query languages to unify Web search and social search, and to support graph pattern association rules for social media marketing. We will revise the conventional theory of tractability and parallel scalability to cope with big data. We will develop new algorithmic foundations and resource-constrained techniques for querying big graphs, by ``making big data small''. When exact answers are beyond reach in big data, we will develop data-driven and query-driven approximation schemes to strike a balance between the accuracy and cost. As a proof of the theory, we will develop GRACE, a system to query big GRAphs within bounded resourCEs, based on the techniques proposed, to support emerging applications such as social media marketing, social search and knowledge bases. A breakthrough in this subject will advance several fields, including big data, theory of computation, parallel computation, and social network analysis.

Fundamental Research



Practical Techniques



Systems



Applications



Survey