Break Iteration Barrier: Parallelize Priority-Based Graph Processing

Many graph processing systems and graph libraries have been developed to process and analyze graph data efficiently. Among the built-in graph algorithms, priority-based graph algorithms, such as Dijkstra's algorithm and greedy algorithms for combination optimization problems, e.g., influence maximization problem, represent a significant category. They can hardly achieve higher efficiency by parallelism due to their inherent iterative dependencies in the priority queue used. Existing parallelization techniques, e.g., parallel priority queues, struggle to preserve the original processing order of these algorithms. They require larger theoretical time complexities or lose the theoretical guarantees associated with these algorithms. To address these issues, in this paper, we propose PQ ⁺ , a priority queue designed to facilitate parallel execution of priority-based graph processing algorithms without altering their inherent process order and preserving the same theoretical time complexity. Extensive experiments on ten real-world datasets across four representative graph processing algorithms validate the effectiveness and efficiency of our proposed approach.