7 papers · 1 filter
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…
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…
Parallel Batch-Dynamic Maximal Matching with Constant Work per Update
Guy E. Blelloch, Andrew C. Brady
We present a work optimal algorithm for parallel fully batch-dynamic maximal matching against an oblivious adversary. It processes batches of updates (either insertions or deletion…
Parallel batch queries on dynamic trees: algorithms and experiments
Humza Ikram, Andrew Brady, Daniel Anderson +1
Dynamic tree data structures maintain a forest while supporting insertion and deletion of edges and a broad set of queries in time per operation. Such data structures a…