9 citations · 20 across the 12 of their papers we have counts for
7 papers · 1 filter
Parallel Contraction Hierarchies Can Be Efficient and Scalable
Zijin Wan, Xiaojun Dong, Letong Wang +3
Contraction Hierarchies (CH) (Geisberger et al., 2008) is one of the most widely used algorithms for shortest-path queries on road networks. Compared to Dijkstra's algorithm, CH en…
Parallel d-tree with Batch Updates
Ziyang Men, Zheqi Shen, Yan Gu +1
The d-tree is one of the most widely used data structures to manage multi-dimensional data. Due to the ever-growing data volume, it is imperative to consider parallelism in d…
Parallel Cluster-BFS and Applications to Shortest Paths
Letong Wang, Guy Blelloch, Yan Gu +1
Breadth-first Search (BFS) is one of the most important graph processing subroutines, especially for computing the unweighted distance. Many applications may require running BFS fr…
Parallel and (Nearly) Work-Efficient Dynamic Programming
Xiangyun Ding, Yan Gu, Yihan Sun
The idea of dynamic programming (DP), proposed by Bellman in the 1950s, is one of the most important algorithmic techniques. However, in parallel, many fundamental and sequentially…
Optimal Parallel Algorithms for Dendrogram Computation and Single-Linkage Clustering
Laxman Dhulipala, Xiaojun Dong, Kishen N Gowda +1
Computing a Single-Linkage Dendrogram (SLD) is a key step in the classic single-linkage hierarchical clustering algorithm. Given an input edge-weighted tree , the SLD of is…
PASGAL: Parallel And Scalable Graph Algorithm Library
Xiaojun Dong, Yan Gu, Yihan Sun +1
In this paper, 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 gra…
Parallel Integer Sort: Theory and Practice
Xiaojun Dong, Laxman Dhulipala, Yan Gu +1
Integer sorting is a fundamental problem in computer science. This paper studies parallel integer sort both in theory and in practice. In theory, we show tighter bounds for a class…