Break Iteration Barrier: Parallelize Priority-Based Graph Processing

Summary: PQ+ enables parallel execution of priority-based graph algorithms while preserving their original processing order and theoretical time complexity, overcoming the iteration barrier of conventional priority queues. Experiments across four algorithms and ten real-world graphs demonstrate its efficiency. (summarized by gpt-6-luna on Oct 22 2026)

Paper ID: h996c960e5a49f932
Venue: SIGMOD
Year: 2027
Pagerank: 4.9605343e-05
Overall Rank: 10,384 | 30.40%
DOI: 10.1145/3837099
PDF: Download (CC BY 4.0)

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Siyi Teng (Chinese University of Hong Kong)
2. Jeffrey Xu Yu (Chinese University of Hong Kong; Hong Kong University of Science and Technology)

BibTeX Citation

@inproceedings{teng_sigmod27,
        title = {{Break Iteration Barrier: Parallelize Priority-Based Graph Processing}},
        author = {Teng, Siyi and Yu, Jeffrey Xu},
        series = {{SIGMOD} '27},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3837099},
        url = {https://dl.acm.org/doi/10.1145/3837099},
        year = {2027}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 13 of 13 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
3	Pregel: A System for Large-Scale Graph Processing	2010	SIGMOD	0.0012089097
22	Distributed GraphLab: A Framework for Machine Learning and Data Mining in the Cloud	2012	VLDB	0.00056028465
187	Influence Maximization: Near-Optimal Time Complexity Meets Practical Efficiency	2014	SIGMOD	0.00025945191
305	Influence Maximization in Near-Linear Time: A Martingale Approach	2015	SIGMOD	0.00021567807
486	From "Think Like a Vertex" to "Think Like a Graph"	2014	VLDB	0.00017462718
902	Parallelizing Sequential Graph Computations	2017	SIGMOD	0.00013142001
931	Blogel: A Block-Centric Framework for Distributed Computation on Real-World Graphs	2014	VLDB	0.00012993132
4,180	Global Reinforcement of Social Networks: The Anchored Coreness Problem	2020	SIGMOD	6.7474268e-05
5,409	Shortest-Path Queries on Complex Networks: Experiments, Analyses, and Improvement	2022	VLDB	6.1320768e-05
8,846	Fast and Space-Efficient Parallel Algorithms for Influence Maximization	2024	VLDB	5.2498988e-05
9,192	Automating Vectorized Distributed Graph Computation	2024	SIGMOD	5.1967502e-05
9,679	Hops Can be Constrained: Efficient Distance Queries on Large Time-Dependent Road Networks	2026	SIGMOD	5.1258854e-05
9,692	Efficient Algorithm for Budgeted Adaptive Influence Maximization: An Incremental RR-set Update Approach	2023	SIGMOD	5.1258854e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	8,095	Parallel k-Core Decomposition: Theory and Practice	2025	SIGMOD
2	4,395	Graph Analytics Through Fine-Grained Parallelism	2016	SIGMOD
3	3,101	Pregel Algorithms for Graph Connectivity Problems with Performance Guarantees	2014	VLDB
4	3,697	Parallel Local Graph Clustering	2016	VLDB
5	1,960	Fast Iterative Graph Computation with Block Updates	2013	VLDB
6	9,428	GraphTwist: Fast Iterative Graph Computation with Two-tier Optimizations	2015	VLDB
7	2,350	Optimizing Graph Algorithms on Pregel-like Systems	2014	VLDB
8	902	Parallelizing Sequential Graph Computations	2017	SIGMOD
9	6,751	Adaptive Asynchronous Parallelization of Graph Algorithms	2018	SIGMOD
10	5,308	Parallel Personalized PageRank on Dynamic Graphs	2018	VLDB