Efficient Subgraph Matching Using GPUs

The explosive growth of various social networks such as Facebook, Twitter, and Instagram has brought in new needs for efficient graph algorithms. As a basic graph operation, subgraph matching is the foundation of many of these algorithms. Consequently, the efficiency of subgraph matching is very important and determines the speed of the whole data mining process. The development of multi-core CPUs allows subgraph matching algorithms to process multiple data at a time. However, the number of threads is still limited, which has become a bottleneck of these CPU-based algorithms. A workaround is using clusters of powerful servers, which normally incurs very expensive network transfer overhead. Therefore, improving the efficiency and parallel abilities of a single computer is a better idea. One of the most effective way to achieve this is making use of GPUs. With the ability of executing thousands of threads simultaneously, GPUs have a great potential to accelerate the subgraph matching. In this paper, we leverage the power of GPUs and propose an efficient subgraph matching algorithm. The experimental results show that our algorithm outperforms the state-of-the-art algorithm by an order of magnitude.