Efficient subgraph matching on billion node graphs

The ability to handle large scale graph data is crucial to an increas-ing number of applications. Much work has been dedicated to sup-porting basic graph operations such as subgraph matching, reach-ability, regular expression matching, etc. In many cases, graph in-dices are employed to speed up query processing. Typically, most indices require either super-linear indexing time or super-linear in-dexing space. Unfortunately, for very large graphs, super-linear approaches are almost always infeasible. In this paper, we study the problem of subgraph matching on billion-node graphs. We present a novel algorithm that supports efficient subgraph match-ing for graphs deployed on a distributed memory store. Instead of relying on super-linear indices, we use efficient graph exploration and massive parallel computing for query processing. Our exper-imental results demonstrate the feasibility of performing subgraph matching on web-scale graph data. 1