Opendata, web and dolomites


Resource Bounded Graph Query Answering

Total Cost €


EC-Contrib. €






Project "GRACE" data sheet

The following table provides information about the project.


Organization address
postcode: EH8 9YL

contact info
title: n.a.
name: n.a.
surname: n.a.
function: n.a.
email: n.a.
telephone: n.a.
fax: n.a.

 Coordinator Country United Kingdom [UK]
 Project website
 Total cost 2˙171˙524 €
 EC max contribution 2˙171˙524 € (100%)
 Programme 1. H2020-EU.1.1. (EXCELLENT SCIENCE - European Research Council (ERC))
 Code Call ERC-2014-ADG
 Funding Scheme ERC-ADG
 Starting year 2015
 Duration (year-month-day) from 2015-11-01   to  2020-10-31


Take a look of project's partnership.

# participants  country  role  EC contrib. [€] 
1    THE UNIVERSITY OF EDINBURGH UK (EDINBURGH) coordinator 2˙171˙524.00


 Project objective

When we search for a product, can we find, using a single query, top choices ranked by Google and at the same time, recommended by our friends connected on Facebook? Is such a query tractable on the social graph of Facebook, which has over 1.31 billion nodes and 170 billion links? Is it feasible to evaluate such a query if we have bounded resources such as time and computing facilities? These questions are challenging: they demand a departure from the traditional query evaluation paradigm and from the classical computational complexity theory, and call for new resource-constrained methodologies to query big graphs.

This project aims to tackle precisely these challenges, from fundamental problems to practical techniques, using radically new approaches. We will develop a graph pattern query language that allows us to, e.g., unify Web search (via keywords) and social search (via graph patterns), and express graph pattern association rules for social media marketing. We will revise the conventional complexity theory to characterize the tractability of queries on big data, and formalize parallel scalability with the increase of processors. We will also develop algorithmic foundations and resource-constrained techniques for querying big graphs, by ``making big data small'. When exact answers are beyond reach in big graphs, 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 answer graph pattern queries on big GRAphs within bounded resourCEs, based on the techniques developed. We envisage that the project will deliver methodological foundations and practical techniques for querying big graphs in general, and for improving search engines and social media marketing in particular. A breakthrough in this subject will advance several fields, including databases, theory of computation, parallel computation and social data analysis.


year authors and title journal last update
List of publications.
2019 Wenfei Fan, Ping Lu, Chao Tian, Jingren Zhou
Deducing certain fixes to graphs
published pages: 752-765, ISSN: 2150-8097, DOI: 10.14778/3317315.3317318
Proceedings of the VLDB Endowment 12/7 2020-03-10
2019 Wenfei Fan, Chunming Hu, Muyang Liu, Ping Lu, Qiang Yin, Jingren Zhou
Dynamic scaling for parallel graph computations
published pages: 877-890, ISSN: 2150-8097, DOI: 10.14778/3324301.3324305
Proceedings of the VLDB Endowment 12/8 2020-03-10
2019 Wenfei Fan, Ping Lu
Dependencies for Graphs
published pages: 1-40, ISSN: 0362-5915, DOI: 10.1145/3287285
ACM Transactions on Database Systems 44/2 2020-03-10
2019 Wenfei Fan
Making big data small
published pages: 20190034, ISSN: 1364-5021, DOI: 10.1098/rspa.2019.0034
Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 475/2225 2020-03-10
2019 Wenfei Fan
Dependencies for Graphs
published pages: 1-12, ISSN: 1936-1955, DOI: 10.1145/3310230
Journal of Data and Information Quality 11/2 2020-03-10
2019 Yang Cao, Wenfei Fan, Tengfei Yuan
Block as a value for SQL over NoSQL
published pages: 1153-1166, ISSN: 2150-8097, DOI: 10.14778/3339490.3339498
Proceedings of the VLDB Endowment 12/10 2020-03-10
2015 Wenfei Fan, Zhe Fan, Chao Tian, Xin Luna Dong
Keys for graphs
published pages: 1590-1601, ISSN: 2150-8097, DOI: 10.14778/2824032.2824056
Proceedings of the VLDB Endowment 8/12 2020-01-24
2017 Yang Cao, Wenfei Fan, Tengfei Yuan
Is Big Data Analytics Beyond the Reach of Small Companies?
published pages: 1-6, ISSN: 0000-0000, DOI: 10.11925/infotech.2096-3467.2017.0723
Journal of Data Analysis and Knowledge Discovery 9 2020-01-24
2016 Wenfei Fan, Xin Wang, Yinghui Wu
Answering Pattern Queries Using Views
published pages: 326-341, ISSN: 1041-4347, DOI: 10.1109/TKDE.2015.2429138
IEEE Transactions on Knowledge and Data Engineering 28/2 2020-01-24
2017 Yang Cao, Wenfei Fan, Shuai Ma
Virtual Network Mapping in Cloud Computing: A Graph Pattern Matching Approach
published pages: , ISSN: 0010-4620, DOI: 10.1093/comjnl/bxw063
The Computer Journal 2020-01-24
2016 Ting Deng, Wenfei Fan, Floris Geerts
Capturing Missing Tuples and Missing Values
published pages: 1-47, ISSN: 0362-5915, DOI: 10.1145/2901737
ACM Transactions on Database Systems 41/2 2020-01-24
2017 Yang Cao and Wenfei Fan
Data Driven Approximation with Bounded Resources
published pages: 973--984, ISSN: 2150-8097, DOI:
Proceedings of the VLDB Endowment Volume 10,number 9, May 2017 m 2020-01-24
2017 Wenfei Fan and Jingbo Xu and Xiaojian Luo and Yinghui Wu and Wenyuan Yu and Ruiqi Xu
GRAPE: Conducting Parallel Graph Computations without Developing Parallel Algorithms
published pages: 30-41, ISSN: 0000-0000, DOI:
IEEE Data Engineering Bulletin 40 2020-01-24
2018 Yang Cao, Wenfei Fan, Floris Geerts, Ping Lu
Bounded Query Rewriting Using Views
published pages: 1-46, ISSN: 0362-5915, DOI: 10.1145/3183673
ACM Transactions on Database Systems 43/1 2020-01-24
2015 Wenfei Fan
Data Quality
published pages: 7-18, ISSN: 0163-5808, DOI: 10.1145/2854006.2854008
ACM SIGMOD Record 44/3 2020-01-24
2015 Wenfei Fan, Xin Wang, Yinghui Wu, Jingbo Xu
Association rules with graph patterns
published pages: 1502-1513, ISSN: 2150-8097, DOI: 10.14778/2824032.2824048
Proceedings of the VLDB Endowment 8/12 2020-01-24
2018 Wenfei Fan and Jingbo Xu and Yinghui Wu and Wenyuan Yu and Jiaxin Jiang
GRAPE: Parallelizing Sequential Graph Computations
published pages: 1889--1892, ISSN: 2150-8097, DOI:
PVLDB 10 2020-01-24
2015 Shuai Ma, Liang Duan, Wenfei Fan, Chunming Hu, Wenguang Chen
Extending Conditional Dependencies with Built-in Predicates
published pages: 3274-3288, ISSN: 1041-4347, DOI: 10.1109/TKDE.2015.2451632
IEEE Transactions on Knowledge and Data Engineering 27/12 2020-01-24
2017 Wenfei Fan, Chunming Hu
Big Graph Analyses: From Queries to Dependencies and Association Rules
published pages: 36-55, ISSN: 2364-1185, DOI: 10.1007/s41019-016-0025-x
Data Science and Engineering 2/1 2020-01-24
2018 Wenfei Fan, Wenyuan Yu, Jingbo Xu, Jingren Zhou, Xiaojian Luo, Qiang Yin, Ping Lu, Yang Cao, Ruiqi Xu
Parallelizing Sequential Graph Computations
published pages: 1-39, ISSN: 0362-5915, DOI: 10.1145/3282488
ACM Transactions on Database Systems 43/4 2020-01-24
2018 Wenfei Fan, Yang Cao, Jingbo Xu, Wenyuan Yu, Yinghui Wu, Chao Tian, Jiaxin Jiang, Bohan Zhang
From Think Parallel to Think Sequential
published pages: 15-22, ISSN: 0163-5808, DOI: 10.1145/3277006.3277011
ACM SIGMOD Record 47/1 2020-01-24
2017 Wenfei Fan, Muyang Liu, Ruiqi Xu, Lei Hou, Dongze Li, Zizhong Meng
Think Sequential, Run Parallel
published pages: 1-25, ISSN: 0302-9743, DOI: 10.1007/978-3-030-01461-2_1
Symposium on Real-Time and Hybrid Systems LNCS 11180 2020-01-24

Are you the coordinator (or a participant) of this project? Plaese send me more information about the "GRACE" project.

For instance: the website url (it has not provided by EU-opendata yet), the logo, a more detailed description of the project (in plain text as a rtf file or a word file), some pictures (as picture files, not embedded into any word file), twitter account, linkedin page, etc.

Send me an  email ( and I put them in your project's page as son as possible.

Thanks. And then put a link of this page into your project's website.

The information about "GRACE" are provided by the European Opendata Portal: CORDIS opendata.

More projects from the same programme (H2020-EU.1.1.)

sociOlfa (2020)

Learning from social scents: from territory to identity

Read More  

SuperH (2019)

Discovery and Characterization of Hydrogen-Based High-Temperature Superconductors

Read More  


Translating the Global Refined Analysis of Newly transcribed RNA and Decay rates by SLAM-seq

Read More