research
∙
06/30/2023
Efficient Parallel Output-Sensitive Edit Distance
Given two strings A[1..n] and B[1..m], and a set of operations allowed t...
share
research
∙
05/07/2023
Scaling Graph-Based ANNS Algorithms to Billion-Size Datasets: A Comparative Analysis
Algorithms for approximate nearest-neighbor search (ANNS) have been the ...
research
∙
04/20/2023
High-Performance and Flexible Parallel Algorithms for Semisort and Related Problems
Semisort is a fundamental algorithmic primitive widely used in the desig...
research
∙
03/08/2023
Parallel Strong Connectivity Based on Faster Reachability
Computing strongly connected components (SCC) is a fundamental problems ...
research
∙
01/03/2023
Provably Fast and Space-Efficient Parallel Biconnectivity
Biconnectivity is one of the most fundamental graph problems. The canoni...
research
∙
08/21/2022
A Work-Efficient Parallel Algorithm for Longest Increasing Subsequence
This paper studies parallel algorithms for the longest increasing subseq...
research
∙
05/25/2022
Many Sequential Iterative Algorithms Can Be Parallel and (Nearly) Work-efficient
To design efficient parallel algorithms, some recent papers showed that ...
research
∙
04/12/2022
PaC-trees: Supporting Parallel and Compressed Purely-Functional Collections
Many modern programming languages are shifting toward a functional style...
research
∙
11/09/2021
Analysis of Work-Stealing and Parallel Cache Complexity
Parallelism has become extremely popular over the past decade, and there...
research
∙
08/05/2021
Space and Time Bounded Multiversion Garbage Collection
We present a general technique for garbage collecting old versions for m...
research
∙
05/13/2021
Efficient Stepping Algorithms and Implementations for Parallel Shortest Paths
In this paper, we study the single-source shortest-path (SSSP) problem w...
research
∙
07/05/2020
Constant-Time Lazy Snapshots Supporting General Queries on Concurrent Data Structures
We present a general transformation that takes any concurrent data struc...
research
∙
03/11/2019
Optimal Parallel Algorithms in the Binary-Forking Model
In this paper we develop optimal algorithms in the binary-forking model ...
research
∙
10/12/2018
Parallelism in Randomized Incremental Algorithms
In this paper we show that many sequential randomized incremental algori...
research
∙
06/27/2018
Algorithmic Building Blocks for Asymmetric Memories
The future of main memory appears to lie in the direction of new non-vol...
research
∙
05/15/2018
Parallel Write-Efficient Algorithms and Data Structures for Computational Geometry
In this paper, we design parallel write-efficient geometric algorithms t...
research
∙
03/23/2018
Parallel Range, Segment and Rectangle Queries with Augmented Maps
The range, segment and rectangle query problems are fundamental problems...
research
∙
03/23/2018
Parallel Range and Segment Queries with Augmented Maps
The range and segment query problems are fundamental problems in computa...
research
∙
03/23/2018