Aquila: Adaptive Parallel Computation of Graph Connectivity Queries

Graph connectivity algorithms answer whether two nodes in a graph are connected under specific conditions, which are beneficial to a number of applications, such as pattern recognition and cybersecurity. Unfortunately, existing graph computing frameworks support only a small number of connectivity algorithms and achieve low computation parallelism. In this paper, we have designed an adaptive parallel computation framework, Aqila, that covers a wide range of different highly optimized graph connectivity algorithms. Given a graph, Aqila first transforms the query if it can be answered with partial computation. During the computation, Aqila is able to greatly reduce the workload by up to 98%. Furthermore, Aqila identifies the irregular tasks in the connectivity algorithms and applies different parallel strategies for different tasks. As a result, Aqila significantly outperforms existing systems such as Multistep, Galois, Ligra, GraphChi, X-Stream, DFS, and Boost, by average 13×, 53×, 264×, 364×, 1, 369×, 45×, and 255×, respectively.