69 citations · 180 across the 26 of their papers we have counts for
29 papers
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…
PIM-tree: A Skew-resistant Index for Processing-in-Memory
Hongbo Kang, Yiwei Zhao, Guy E. Blelloch +4
The performance of today's in-memory indexes is bottlenecked by the memory latency/bandwidth wall. Processing-in-memory (PIM) is an emerging approach that potentially mitigates thi…