Paper Info
Title
Querying big graphs within bounded resources
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 α.
Year
DOI
Venue
2014
10.1145/2588555.2610513
SIGMOD Conference
Keywords
Field
DocType
bounded resource,graph querying,miscellaneous,pattern matching
Data mining,Graph,Locality,Computer science,Reachability,Theoretical computer science,Synthetic data,Pattern matching,Subgraph isomorphism problem,Database,Bounded function
Conference
Citations 
PageRank 
References 
23
0.69
31
Authors
3
Name
Order
Citations
PageRank
Wenfei Fan14154197.29
xin wang21857.35
Yinghui Wu382442.79