Efficient Subgraph Matching on Billion Node Graphs by Zhao Sun (Fudan University, China), Hongzhi Wang (Harbin Institute of Technology, China), Haixun Wang (Microsoft Research Asia, China), Bin Shao (Microsoft Research Asia, China) and Jianzhong Li (Harbin Institute of Technology, China).
Abstract:
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, we study the problem of subgraph matching on billion-node graphs. We present a novel algorithm that supports efficient subgraph matching 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 experimental results demonstrate the feasibility of performing subgraph matching on web-scale graph data.
Did you say you were interested in parallel graph processing?
This paper and the materials cited in the bibliography make a nice introduction to the current options for graph processing.
I first saw this at Alex Popescu’s myNoSQL, citing it from the VLDB proceedings.
With the DBLP enhanced version of the VLDB proceedings, VLDB 2012 Ice Breaker v0.1, DBLP links for the authors were easy.
[…] trying to recover from learning about scalable subgraph matching, Efficient Subgraph Matching on Billion Node Graphs [Parallel Graph Processing], and now the nice folks at Tokutek post a 26,816% query performance increase for […]
Pingback by 268x Query Performance Bump for MongoDB « Another Word For It — September 2, 2012 @ 6:24 pm