Querying Big Graphs Within Bounded Resources

Wenfei Fan, Xin Wang, Yinghui Wu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract / Description of output

This paper studies the problem of querying graphs within bounded resources. Given a query Q, a graph G and a small ratio α, it aims to answer Q in G by accessing only a fraction GQ of G of size |GQ| ≤ α |G|. The need for this is evident when G is big while our available resources are limited, as indicated by α. We propose resource-bounded query answering via a dynamic scheme that reduces big G to GQ. We investigate when we can find the exact answers Q(G) from GQ, and if GQ cannot accommodate enough information, how accurate the approximate answers Q(GQ) are. To verify the effectiveness of the approach, we study two types of queries. One consists of pattern queries that have data locality, such as subgraph isomorphism and strong simulation. The other is the class of reachability queries, without data locality. We show that it is hard to get resource-bounded algorithms with 100% accuracy: NP-hard for pattern queries, and non-existing for reachability when α ≠ 1. Despite these, we develop resource-bounded algorithms for answering these queries. Using real-life and synthetic data, we experimentally evaluate the performance of the algorithms. We find that they scale well for both types of queries, and our approximate answers are accurate, even 100% for small α.
Original languageEnglish
Title of host publicationProceedings of the 2014 ACM SIGMOD International Conference on Management of Data
Place of PublicationNew York, NY, USA
Number of pages12
ISBN (Print)978-1-4503-2376-5
Publication statusPublished - 2014

Keywords / Materials (for Non-textual outputs)

  • bounded resource, graph querying, pattern matching


Dive into the research topics of 'Querying Big Graphs Within Bounded Resources'. Together they form a unique fingerprint.

Cite this