COSI: Cloud Oriented Subgraph Identification in Massive Social Networks

Subgraph matching is a key operation on graph data. Social Network (SN) providers may want to find all subgraphs within their social network that "Match" certain query graph patterns. Unfortunately, subgraph matching is NP-complete, making its application to massive SNs a major challenge. Past work has shown how to implement subgraph matching on a single processor when the graph has 10-25M edges. This paper shows how to use cloud computing in conjunction with such existing single processor methods to efficiently match complex subgraphs on graphs as large as 778M edges. A cloud consists of one "Master" compute node and k "Slave" compute nodes.