Subgraph Querying in Relational Networks: A MapReduce Approach

Querying/enumerating sub graphs in a network which are isomorphic to a template is a key problem in many data intensive applications. In this paper, we propose a dynamic programming algorithm and its MapReduce version, targeting on enumerating sub graphs in massive networks. For tree let counting, a sub-problem of sub graph enumeration, we integrate an approximation algorithm called color coding to simplify the computation. Our approach is amenable to the cloud computing environment and scales to real-world problems that involve complicated sub graph querying in vast amount of data, e.g., SPARQL querying in distributed RDF stores for semantic web mining.