Xiaojun Dong
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Research Interests
Xiaojun Dong has a total of 13 co-authors. Here are the top co-authors by number of shared publications:
- Yan Gu
University of California, Riverside, Riverside, USA
14 shared publications - Yihan Sun
UC Riverside
13 shared publications - Letong Wang
UC Riverside
6 shared publications - Laxman Dhulipala
University of Maryland, College Park, College PARK, USA
4 shared publications - Youzhe Liu
UC Riverside
3 shared publications - Enzuo Zhu
UC Davis
2 shared publications
Latest Publications
- Open Access
- 28 July 2025
- Published by Association for Computing Machinery (ACM)
- p. 13-15
Parallel Contraction Hierarchies Can Be Efficient and Scalable (Abstract)
- 28 July 2025
- Published by Association for Computing Machinery (ACM)
- p. 13-15
Open AccessParallel Contraction Hierarchies Can Be Efficient and Scalable (Abstract)
- Open Access
- 28 July 2025
- Published by Association for Computing Machinery (ACM)
- p. 10-12
Parallel k-Core Decomposition: Theory and Practice (Abstract)
- 28 July 2025
- Published by Association for Computing Machinery (ACM)
- p. 10-12
Open AccessParallel k-Core Decomposition: Theory and Practice (Abstract)
- Open Access
- 16 July 2025
- Published by Association for Computing Machinery (ACM)
- p. 458-472
Parallel Point-to-Point Shortest Paths and Batch Queries
- 16 July 2025
- Published by Association for Computing Machinery (ACM)
- p. 458-472
Open AccessParallel Point-to-Point Shortest Paths and Batch Queries
- Open Access
- 17 June 2025
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Management of Data
- Vol. 3 (3) , 1-27
Parallel k -Core Decomposition: Theory and Practice
This paper proposes efficient solutions for k -core decomposition with high parallelism. The problem of k -core decomposition is fundamental in graph analysis and has applications across various domains. However, existing algorithms face significant challenges in achieving work-efficiency in theory and/or high parallelism in practice, and suffer from various performance bottlenecks. We present a simple, work-efficient parallel framework for k -core decomposition that is easy to implement and adaptable to various strategies for improving work-efficiency. We introduce two techniques to enhance parallelism: a sampling scheme to reduce contention on high-degree vertices, and vertical granularity control (VGC) to mitigate scheduling overhead for low-degree vertices. Furthermore, we design a hierarchical bucket structure to optimize performance for graphs with high coreness values. We evaluate our algorithm on a diverse set of real-world and synthetic graphs. Compared to state-of-the-art parallel algorithms, including ParK, PKC, and Julienne, our approach demonstrates superior performance on 23 out of 25 graphs when tested on a 96-core machine. Our algorithm shows speedups of up to 315× over ParK, 33.4× over PKC, and 52.5× over Julienne.
- 17 June 2025
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Management of Data
- Vol. 3 (3) , 1-27
Open AccessParallel k -Core Decomposition: Theory and Practice
This paper proposes efficient solutions for k -core decomposition with high parallelism. The problem of k -core decomposition is fundamental in graph analysis and has applications across various domains. However, existing algorithms face significant challenges in achieving work-efficiency in theory and/or high parallelism in practice, and suffer from various performance bottlenecks. We present a simple, work-efficient parallel framework for k -core decomposition that is easy to implement and adaptable to various strategies for improving work-efficiency. We introduce two techniques to enhance parallelism: a sampling scheme to reduce contention on high-degree vertices, and vertical granularity control (VGC) to mitigate scheduling overhead for low-degree vertices. Furthermore, we design a hierarchical bucket structure to optimize performance for graphs with high coreness values. We evaluate our algorithm on a diverse set of real-world and synthetic graphs. Compared to state-of-the-art parallel algorithms, including ParK, PKC, and Julienne, our approach demonstrates superior performance on 23 out of 25 graphs when tested on a 96-core machine. Our algorithm shows speedups of up to 315× over ParK, 33.4× over PKC, and 52.5× over Julienne.
- Open Access
- 8 June 2025
- Published by Association for Computing Machinery (ACM)
- p. 670-688
Parallel Contraction Hierarchies Can Be Efficient and Scalable
- 8 June 2025
- Published by Association for Computing Machinery (ACM)
- p. 670-688
Open AccessParallel Contraction Hierarchies Can Be Efficient and Scalable
- Open Access
- 21 March 2025
- Published by Association for Computing Machinery (ACM)
- p. 82-84
Reproducibility Report for ACM SIGMOD 2024 Paper: 'On Efficient Large Sparse Matrix Chain Multiplication'
- 21 March 2025
- Published by Association for Computing Machinery (ACM)
- p. 82-84
Open AccessReproducibility Report for ACM SIGMOD 2024 Paper: 'On Efficient Large Sparse Matrix Chain Multiplication'
- Open Access
- 17 June 2024
- Published by Association for Computing Machinery (ACM)
- p. 13-14
Parallel Integer Sort: Theory and Practice (Abstract) | Proceedings of the 2024 ACM Workshop on Highlights of Parallel Computing
This paper studies parallel integer sort both in theory and in practice. In theory, we show tighter bounds for a class of existing practical integer sort algorithms, which provides a solid theoretical foundation for their widespread usage in practice and strong performance. In practice, we design a new integer sorting algorithm, DovetailSort, that is theoretically efficient and has good practical performance.
- 17 June 2024
- Published by Association for Computing Machinery (ACM)
- p. 13-14
Open AccessParallel Integer Sort: Theory and Practice (Abstract) | Proceedings of the 2024 ACM Workshop on Highlights of Parallel Computing
This paper studies parallel integer sort both in theory and in practice. In theory, we show tighter bounds for a class of existing practical integer sort algorithms, which provides a solid theoretical foundation for their widespread usage in practice and strong performance. In practice, we design a new integer sorting algorithm, DovetailSort, that is theoretically efficient and has good practical performance.
- Open Access
- 17 June 2024
- Published by Association for Computing Machinery (ACM)
- p. 17-18
Efficient Parallel Output-Sensitive Edit Distance (Abstract) | Proceedings of the 2024 ACM Workshop on Highlights of Parallel Computing
We study efficient parallel algorithms for output-sensitive edit distance, achieving asymptotically better cost bounds than the standard Θ(nm) dynamic programming algorithm when the edit distance is small. All of the algorithms studied in this paper have good theoretical guarantees, and achieve different tradeoffs between work, span, and space. We test and compare our algorithms on both synthetic data and real-world data.
- 17 June 2024
- Published by Association for Computing Machinery (ACM)
- p. 17-18
Open AccessEfficient Parallel Output-Sensitive Edit Distance (Abstract) | Proceedings of the 2024 ACM Workshop on Highlights of Parallel Computing
We study efficient parallel algorithms for output-sensitive edit distance, achieving asymptotically better cost bounds than the standard Θ(nm) dynamic programming algorithm when the edit distance is small. All of the algorithms studied in this paper have good theoretical guarantees, and achieve different tradeoffs between work, span, and space. We test and compare our algorithms on both synthetic data and real-world data.
- Open Access
- 17 June 2024
- Published by Association for Computing Machinery (ACM)
- p. 439-441
Brief Announcement: PASGAL: Parallel And Scalable Graph Algorithm Library
We introduce PASGAL (Parallel And Scalable Graph Algorithm Library), a parallel graph library that scales to a variety of graph types, many processors, and large graphs. One special focus of PASGAL is the efficiency onlarge-diameter graphs, which is a common challenge for many existing parallel graph processing systems due to the high overhead in synchronizing threads when traversing the graph in the breadth-first order. The core idea in PASGAL is a technique calledvertical granularity control (VGC) to hide synchronization overhead by careful algorithm redesign and new data structures. We compare PASGAL with existing parallel implementations on several fundamental graph problems. PASGAL is always competitive on small-diameter graphs, and is significantly faster on large-diameter graphs.
- 17 June 2024
- Published by Association for Computing Machinery (ACM)
- p. 439-441
Open AccessBrief Announcement: PASGAL: Parallel And Scalable Graph Algorithm Library
We introduce PASGAL (Parallel And Scalable Graph Algorithm Library), a parallel graph library that scales to a variety of graph types, many processors, and large graphs. One special focus of PASGAL is the efficiency onlarge-diameter graphs, which is a common challenge for many existing parallel graph processing systems due to the high overhead in synchronizing threads when traversing the graph in the breadth-first order. The core idea in PASGAL is a technique calledvertical granularity control (VGC) to hide synchronization overhead by careful algorithm redesign and new data structures. We compare PASGAL with existing parallel implementations on several fundamental graph problems. PASGAL is always competitive on small-diameter graphs, and is significantly faster on large-diameter graphs.
- Open Access
- 17 June 2024
- Published by Association for Computing Machinery (ACM)
- p. 233-245
Optimal Parallel Algorithms for Dendrogram Computation and Single-Linkage Clustering
Computing a Single-Linkage Dendrogram (SLD) is a key step in the classic single-linkage hierarchical clustering algorithm. Given an input edge-weighted tree T, the SLD of T is a binary dendrogram that summarizes the n-1 clusterings obtained by contracting the edges of T in order of weight. Existing algorithms for computing the SLD all require Ømega(nłog n) work where n = |T|. Furthermore, to the best of our knowledge no prior work provides a parallel algorithm obtaining non-trivial speedup for this problem. In this paper, we design faster parallel algorithms for computing SLDs both in theory and in practice based on new structural results about SLDs. In particular, we obtain a deterministic output-sensitive parallel algorithm based on parallel tree contraction that requires O(n łog h) work and O(łog^2 n łog^2 h) depth, where h is the height of the output SLD. We also give a deterministic bottom-up algorithm for the problem inspired by the nearest-neighbor chain algorithm for hierarchical agglomerative clustering, and show that it achieves O(nłog h) work and O(h łog n) depth. Our results are based on a novel divide-and-conquer framework for building SLDs, inspired by divide-and-conquer algorithms for Cartesian trees. Our new algorithms can quickly compute the SLD on billion-scale trees, and obtain up to 150x speedup over the highly-efficient Union-Find algorithm typically used to compute SLDs in practice.
- 17 June 2024
- Published by Association for Computing Machinery (ACM)
- p. 233-245
Open AccessOptimal Parallel Algorithms for Dendrogram Computation and Single-Linkage Clustering
Computing a Single-Linkage Dendrogram (SLD) is a key step in the classic single-linkage hierarchical clustering algorithm. Given an input edge-weighted tree T, the SLD of T is a binary dendrogram that summarizes the n-1 clusterings obtained by contracting the edges of T in order of weight. Existing algorithms for computing the SLD all require Ømega(nłog n) work where n = |T|. Furthermore, to the best of our knowledge no prior work provides a parallel algorithm obtaining non-trivial speedup for this problem. In this paper, we design faster parallel algorithms for computing SLDs both in theory and in practice based on new structural results about SLDs. In particular, we obtain a deterministic output-sensitive parallel algorithm based on parallel tree contraction that requires O(n łog h) work and O(łog^2 n łog^2 h) depth, where h is the height of the output SLD. We also give a deterministic bottom-up algorithm for the problem inspired by the nearest-neighbor chain algorithm for hierarchical agglomerative clustering, and show that it achieves O(nłog h) work and O(h łog n) depth. Our results are based on a novel divide-and-conquer framework for building SLDs, inspired by divide-and-conquer algorithms for Cartesian trees. Our new algorithms can quickly compute the SLD on billion-scale trees, and obtain up to 150x speedup over the highly-efficient Union-Find algorithm typically used to compute SLDs in practice.