Yihan Sun
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Yihan Sun has a total of 19 co-authors. Here are the top co-authors by number of shared publications:
- Yan Gu
University of California, Riverside, Riverside, USA
22 shared publications - Xiaojun Dong
UC Riverside
13 shared publications - Letong Wang
UC Riverside
8 shared publications - Guy E. Blelloch
Carnegie Mellon University
4 shared publications - Laxman Dhulipala
University of Maryland, College Park, College PARK, USA
4 shared publications - Xiangyun Ding
University of California, Riverside, Riverside, USA
4 shared publications
Latest Publications
- Open Access
- 6 July 2026
- Published by Association for Computing Machinery (ACM)
- p. 182-195
Parallel Metric Skip Lists and Nearest Neighbor Search
The metric skip list is a data structure designed for efficient nearest and k-nearest neighbor search in metric spaces. For many real-world datasets with reasonable distributions—specifically, those with a constant expansion rate—it supports Õ(n) construction time and O(k log n) query time, where n is the input size and k is the number of nearest neighbors in queries. Notably, unlike alternative approaches, it does not require a bounded aspect ratio, making it more flexible for input data distributions. However, the inherently sequential nature of its original construction has, to our knowledge, precluded any existing parallel algorithm. In this paper, we present highly parallel and work-efficient algorithms for constructing metric skip lists. Under the assumption of a constant expansion rate, our approach achieves an expected work of O(n log n) and a polylogarithmic span with high probability. Our design is based on novel algorithmic insights that improves the sequential procedure, enabling a divide-and-conquer strategy that facilitates parallelism while maintaining efficiency. With our algorithms, we can also support improved bounds for relevant applications using nearest neighbor as building blocks, including bichromatic closest pair (BCP), density-based clustering, and k-NN graph construction, among others. To our knowledge, many of these results represent the first solutions to achieve both work efficiency and polylogarithmic span, relying solely on the assumption of a constant expansion rate.
- 6 July 2026
- Published by Association for Computing Machinery (ACM)
- p. 182-195
Open AccessParallel Metric Skip Lists and Nearest Neighbor Search
The metric skip list is a data structure designed for efficient nearest and k-nearest neighbor search in metric spaces. For many real-world datasets with reasonable distributions—specifically, those with a constant expansion rate—it supports Õ(n) construction time and O(k log n) query time, where n is the input size and k is the number of nearest neighbors in queries. Notably, unlike alternative approaches, it does not require a bounded aspect ratio, making it more flexible for input data distributions. However, the inherently sequential nature of its original construction has, to our knowledge, precluded any existing parallel algorithm. In this paper, we present highly parallel and work-efficient algorithms for constructing metric skip lists. Under the assumption of a constant expansion rate, our approach achieves an expected work of O(n log n) and a polylogarithmic span with high probability. Our design is based on novel algorithmic insights that improves the sequential procedure, enabling a divide-and-conquer strategy that facilitates parallelism while maintaining efficiency. With our algorithms, we can also support improved bounds for relevant applications using nearest neighbor as building blocks, including bichromatic closest pair (BCP), density-based clustering, and k-NN graph construction, among others. To our knowledge, many of these results represent the first solutions to achieve both work efficiency and polylogarithmic span, relying solely on the assumption of a constant expansion rate.
- Open Access
- 28 January 2026
- Published by Association for Computing Machinery (ACM)
- p. 150-163
Parallel Dynamic Spatial Indexes
- 28 January 2026
- Published by Association for Computing Machinery (ACM)
- p. 150-163
Open AccessParallel Dynamic Spatial Indexes
- Open Access
- 28 July 2025
- Published by Association for Computing Machinery (ACM)
- p. 4-6
Parallel kd-tree with Batch Updates (Abstract)
- 28 July 2025
- Published by Association for Computing Machinery (ACM)
- p. 4-6
Open AccessParallel kd-tree with Batch Updates (Abstract)
- Open Access
- 28 July 2025
- Published by Association for Computing Machinery (ACM)
- p. 19-21
Parallel Cluster-BFS and Applications to Shortest Paths
- 28 July 2025
- Published by Association for Computing Machinery (ACM)
- p. 19-21
Open AccessParallel Cluster-BFS and Applications to Shortest Paths
- 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
- 10 February 2025
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Management of Data
- Vol. 3 (1) , 1-26
Parallel kd-tree with Batch Updates
The kd-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 kd-trees. However, we observed challenges in existing parallel kd-tree implementations, for both constructions and updates. The goal of this paper is to develop efficient in-memory kd-trees by supporting high parallelism and cache-efficiency. We propose the Pkd-tree (Parallel kd-tree), a parallel kd-tree that is efficient both in theory and in practice. The Pkd-tree supports parallel tree construction, batch update (insertion and deletion), and various queries including k -nearest neighbor search, range query, and range count. We proved that our algorithms have strong theoretical bounds in work (sequential time complexity), span (parallelism), and cache complexity. Our key techniques include 1) an efficient construction algorithm that optimizes work, span, and cache complexity simultaneously, and 2) reconstruction-based update algorithms that guarantee the tree to be weight-balanced. With the new algorithmic insights and careful engineering effort, we achieved a highly optimized implementation of the Pkd-tree. We tested Pkd-tree with various synthetic and real-world datasets, including both uniform and highly skewed data. We compare the Pkd-tree with state-of-the-art parallel kd-tree implementations. In all tests, with better or competitive query performance, Pkd-tree is much faster in construction and updates consistently than all baselines. We released our code.
- 10 February 2025
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Management of Data
- Vol. 3 (1) , 1-26
Open AccessParallel kd-tree with Batch Updates
The kd-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 kd-trees. However, we observed challenges in existing parallel kd-tree implementations, for both constructions and updates. The goal of this paper is to develop efficient in-memory kd-trees by supporting high parallelism and cache-efficiency. We propose the Pkd-tree (Parallel kd-tree), a parallel kd-tree that is efficient both in theory and in practice. The Pkd-tree supports parallel tree construction, batch update (insertion and deletion), and various queries including k -nearest neighbor search, range query, and range count. We proved that our algorithms have strong theoretical bounds in work (sequential time complexity), span (parallelism), and cache complexity. Our key techniques include 1) an efficient construction algorithm that optimizes work, span, and cache complexity simultaneously, and 2) reconstruction-based update algorithms that guarantee the tree to be weight-balanced. With the new algorithmic insights and careful engineering effort, we achieved a highly optimized implementation of the Pkd-tree. We tested Pkd-tree with various synthetic and real-world datasets, including both uniform and highly skewed data. We compare the Pkd-tree with state-of-the-art parallel kd-tree implementations. In all tests, with better or competitive query performance, Pkd-tree is much faster in construction and updates consistently than all baselines. We released our code.