Shuo Han's paper (Speeding Up Set Intersections in Graph Algorithms using SIMD Instructions) is accepted by SIGMOD 2018.

In this paper, we focus on accelerating a widely employed computing pattern --- set intersection, to boost a group of graph algorithms. Graph’s adjacency-lists can be naturally considered as node sets, thus set intersection is a primitive operation in many graph algorithms. We propose QFilter, a set intersection algorithm which can quickly filter out most of unnecessary comparisons in one byte-checking step by SIMD instructions. We also present a binary representation called BSR that encodes sets in a compact layout. By combining QFilter and BSR, we achieve data parallelism in two levels — inter-chunk and intra-chunk parallelism. Moreover, we find that node ordering impacts the performance of intersection by affecting the compactness of BSR. We formulate the graph reordering problem as an optimization of the compactness of BSR, and prove its strong NP-completeness. Thus we propose an approximate algorithm that can find a better ordering to enhance the intra-chunk parallelism. Extensive experiments on both synthetic and real datasets confirm that our approach can improve the performance of set intersection in graph algorithms significantly.