55 citations · 196 across the 38 of their papers we have counts for
40 papers
ANNLib: A Development Framework for Efficient Approximate Nearest Neighbor Search
Zheqi Shen, Jingbo Su, Zijin Wan +2
Approximate Nearest Neighbor Search (ANNS) plays a pivotal role in modern deep learning pipelines. Recently, many ANNS systems have been proposed to provide broad, flexible functio…
Parallel Metric Skip Lists and Nearest Neighbor Search
Xiangyun Ding, Rohin Garg, Yan Gu +1
The metric skip-list is a data structure designed for efficient nearest and -nearest neighbor search in metric spaces. For many real-world datasets with reasonable distributions…
On Worst-Case Optimal Polynomial Intersection
Yihang Sun, Mary Wootters
The Optimal Polynomial Intersection (OPI) problem is the following: Given sets and evaluation points , find…
Parallel Dynamic Spatial Indexes
Ziyang Men, Bo Huang, Yan Gu +1
Maintaining spatial data (points in two or three dimensions) is crucial and has a wide range of applications, such as graphics, GIS, and robotics. To handle spatial data, many data…
Parallel Joinable B-Trees in the Fork-Join I/O Model
Michael Goodrich, Yan Gu, Ryuto Kitagawa +1
Balanced search trees are widely used in computer science to efficiently maintain dynamic ordered data. To support efficient set operations (e.g., union, intersection, difference)…
Parallel Point-to-Point Shortest Paths and Batch Queries
Xiaojun Dong, Andy Li, Yan Gu +1
We propose Orionet, efficient parallel implementations of Point-to-Point Shortest Paths (PPSP) queries using bidirectional search (BiDS) and other heuristics, with an additional fo…
New Algorithms for Incremental Minimum Spanning Trees and Temporal Graph Applications
Xiangyun Ding, Yan Gu, Yihan Sun
Processing graphs with temporal information (the temporal graphs) has become increasingly important in the real world. In this paper, we study efficient solutions to temporal graph…
Parallel -Core Decomposition: Theory and Practice
Youzhe Liu, Xiaojun Dong, Yan Gu +1
This paper proposes efficient solutions for -core decomposition with high parallelism. The problem of -core decomposition is fundamental in graph analysis and has application…
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…
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…
Fast and Space-Efficient Parallel Algorithms for Influence Maximization
Letong Wang, Xiangyun Ding, Yan Gu +1
Influence Maximization (IM) is a crucial problem in data science. The goal is to find a fixed-size set of highly-influential seed vertices on a network to maximize the influence sp…
Efficient Parallel Output-Sensitive Edit Distance
Xiangyun Ding, Xiaojun Dong, Yan Gu +2
Given two strings and , and a set of operations allowed to edit the strings, the edit distance between and is the minimum number of operations required t…
ParlayANN: Scalable and Deterministic Parallel Graph-Based Approximate Nearest Neighbor Search Algorithms
Magdalen Dobson Manohar, Zheqi Shen, Guy E. Blelloch +4
Approximate nearest-neighbor search (ANNS) algorithms are a key part of the modern deep learning stack due to enabling efficient similarity search over high-dimensional vector spac…
High-Performance and Flexible Parallel Algorithms for Semisort and Related Problems
Xiaojun Dong, Yunshu Wu, Zhongqi Wang +3
Semisort is a fundamental algorithmic primitive widely used in the design and analysis of efficient parallel algorithms. It takes input as an array of records and a function extrac…
Parallel Strong Connectivity Based on Faster Reachability
Letong Wang, Xiaojun Dong, Yan Gu +1
Computing strongly connected components (SCC) is a fundamental problems in graph processing. As today's real-world graphs are getting larger and larger, parallel SCC is increasingl…
Provably Fast and Space-Efficient Parallel Biconnectivity
Xiaojun Dong, Letong Wang, Yan Gu +1
Biconnectivity is one of the most fundamental graph problems. The canonical parallel biconnectivity algorithm is the Tarjan-Vishkin algorithm, which has optimal work (numb…
Parallel Longest Increasing Subsequence and van Emde Boas Trees
Yan Gu, Ziyang Men, Zheqi Shen +2
This paper studies parallel algorithms for the longest increasing subsequence (LIS) problem. Let be the input size and be the LIS length of the input. Sequentially, LIS is…
Many Sequential Iterative Algorithms Can Be Parallel and (Nearly) Work-efficient
Zheqi Shen, Zijin Wan, Yan Gu +1
To design efficient parallel algorithms, some recent papers showed that many sequential iterative algorithms can be directly parallelized but there are still challenges in achievin…
PaC-trees: Supporting Parallel and Compressed Purely-Functional Collections
Laxman Dhulipala, Guy E. Blelloch, Yan Gu +1
Many modern programming languages are shifting toward a functional style for collection interfaces such as sets, maps, and sequences. Functional interfaces offer many advantages, i…
Analysis of Work-Stealing and Parallel Cache Complexity
Yan Gu, Zachary Napier, Yihan Sun
Parallelism has become extremely popular over the past decade, and there have been a lot of new parallel algorithms and software. The randomized work-stealing (RWS) scheduler plays…