13 papers
Optimal Time-Space Tradeoff for Dynamic Difference-Encoded Dictionaries
Guy E. Blelloch, Yang Hu, William Kuszmaul +2
The dynamic dictionary is a fundamental data structure that maintains a set of size (we assume ), supporting insertions, deletions and membership q…
Dynamic Entropy-Encoded Arrays in O(1) Time with Nearly Optimal Space
Guy E. Blelloch, Yang Hu, William Kuszmaul +2
We show how to implement a dynamic array with symbols from a fixed alphabet , while supporting -time queries and updates, and using a total space of $$ \log \bin…
uSTM: A Lightweight and Efficient STM Supporting General Types and Deferred Aborts
Zachary Kent, Guy Blelloch, André Costa
Software Transactional Memory (STM) systems allow developers to more easily exploit multicore architectures by wrapping arbitrary sequential code in transactions that are executed…
Fast Concurrent Primitives Despite Contention
Michael A. Bender, Guy E. Blelloch, Martin Farach-Colton +4
We study the problem of constructing concurrent objects in a setting where processes run in parallel and interact through a shared memory that is subject to write contention. O…
Parallel Batch-Dynamic Maximal Independent Set
Guy Blelloch, Andrew Brady, Laxman Dhulipala +2
We develop the first theoretically-efficient algorithm for maintaining the maximal independent set (MIS) of a graph in the parallel batch-dynamic setting. In this setting, a graph…
Faster Parallel Batch-Dynamic Algorithms for Low Out-Degree Orientation
Guy Blelloch, Andrew Brady, Laxman Dhulipala +3
A low out-degree orientation directs each edge of an undirected graph with the goal of minimizing the maximum out-degree of a vertex. In the parallel batch-dynamic setting, one can…