Edinburgh Research Explorer

Querying Big Graphs Within Bounded Resources

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

Related Edinburgh Organisations

Open Access permissions

Open

Documents

http://doi.acm.org/10.1145/2588555.2610513
Original languageEnglish
Title of host publicationProceedings of the 2014 ACM SIGMOD International Conference on Management of Data
Place of PublicationNew York, NY, USA
PublisherACM
Pages301-312
Number of pages12
ISBN (Print)978-1-4503-2376-5
DOIs
Publication statusPublished - 2014

Abstract

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 α.

    Research areas

  • bounded resource, graph querying, pattern matching

Download statistics

No data available

ID: 17266064