research
∙
06/14/2023
Deterministic and Work-Efficient Parallel Batch-Dynamic Trees in Low Span
Dynamic trees are a well-studied and fundamental building block of dynam...
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
∙
12/27/2022
Practically and Theoretically Efficient Garbage Collection for Multiversioning
Multiversioning is widely used in databases, transactional memory, and c...
research
∙
11/18/2022
PIM-tree: A Skew-resistant Index for Processing-in-Memory
The performance of today's in-memory indexes is bottlenecked by the memo...
research
∙
04/12/2022
PaC-trees: Supporting Parallel and Compressed Purely-Functional Collections
Many modern programming languages are shifting toward a functional style...
research
∙
04/12/2022
Turning Manual Concurrent Memory Reclamation into Automatic Reference Counting
Safe memory reclamation (SMR) schemes are an essential tool for lock-fre...
research
∙
01/03/2022
Lock-Free Locks Revisited
This paper presents a new and practical approach to lock-free locks base...
research
∙
08/10/2021
Fast and Fair Lock-Free Locks
We present a randomized approach for lock-free locks with strong bounds ...
research
∙
08/09/2021
FliT: A Library for Simple and Efficient Persistent Algorithms
Non-volatile random access memory (NVRAM) offers byte-addressable persis...
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/14/2021
Efficient Parallel Self-Adjusting Computation
Self-adjusting computation is an approach for automatically producing dy...
research
∙
02/10/2021
Parallel Minimum Cuts in O(m log^2(n)) Work and Low Depth
We present an O(m log^2(n)) work, O(polylog(n)) depth parallel algorithm...
research
∙
08/10/2020
Concurrent Fixed-Size Allocation and Free in Constant Time
Our goal is to efficiently solve the dynamic memory allocation problem i...
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
∙
04/06/2020
NVTraverse: In NVRAM Data Structures, the Destination is More Important than the Journey
The recent availability of fast, dense, byte-addressable non-volatile me...
research
∙
02/17/2020
Concurrent Reference Counting and Resource Management in Wait-free Constant Time
A common problem when implementing concurrent programs is efficiently pr...
research
∙
02/13/2020
Work-efficient Batch-incremental Minimum Spanning Trees with Applications to the Sliding Window Model
Algorithms for dynamically maintaining minimum spanning trees (MSTs) hav...
research
∙
02/12/2020
Batch-dynamic Algorithms via Parallel Change Propagation and Applications to Dynamic Trees
Dynamic algorithms capable of supporting batches of updates are increasi...
research
∙
11/21/2019
LL/SC and Atomic Copy: Constant Time, Space Efficient Implementations using only pointer-width CAS
The Load-Link/Store-Conditional (LL/SC) primitive is considered the most...
research
∙
10/27/2019
Semi-Asymmetric Parallel Graph Algorithms for NVRAMs
Emerging non-volatile main memory (NVRAM) technologies provide novel fea...
research
∙
03/21/2019
Parallel Batch-Dynamic Graph Connectivity
With the rapid growth of graph datasets over the past decade, a new kind...
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
∙
06/12/2018
Making Concurrent Algorithms Detectable
Non-volatile memory (NVM) promises persistent main memory that remains c...
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
∙
05/15/2018
The Parallel Persistent Memory Model
We consider a parallel computational model that consists of P processors...
research
∙
05/14/2018
Theoretically Efficient Parallel Graph Algorithms Can Be Fast and Scalable
There has been significant interest in parallel graph processing recentl...
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