11 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 either provide broad functional…
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…
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…
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…
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 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…