This is the authors' abstract. We don't add key points for this paper.
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 13x, 53x, 264x, 364x, 1,369x, 45x, and 255x, respectively.
Answers are grounded in this paper and cite their sources.
No takes yet. Share an insight, caveat, or question.
Ji et al. (2020) studied this question.
Synapse has enriched 8 closely related papers on similar clinical questions. Consider them for comparative context: