Efficient Subgraph Matching on Billion Node Graphs
The ability to handle large scale graph data is crucial to an increasing number of applications. Much work has been dedicated to supporting basic graph operations such as subgraph matching, reachability, regular expression matching, etc. In many cases, graph indices are employed to speed up query processing. Typically, most indices require either super-linear indexing time or super-linear indexing space. Unfortunately, for very large graphs, super-linear approaches are almost always infeasible. In this paper, the authors study the problem of subgraph matching on billion-node graphs. They present a novel algorithm that supports efficient subgraph matching for graphs deployed on a distributed memory store.