Querying big graphs within bounded resources

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 frac-tion GQ of G of size |GQ | ≤ α|G|. The need for this is evident when G is big while our available resources are lim-ited, 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 informa-tion, 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 lo-cality, 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 al-gorithms with 100 % accuracy: NP-hard for pattern queries, and non-existing for reachability when α 6 = 1. Despite these, we develop resource-bounded algorithms for answering these queries. Using real-life and synthetic data, we experimen-tally evaluate the performance of the algorithms. We find that they scale well for both types of queries, and our ap-proximate answers are accurate, even 100 % for small α