From the 1 of 11 linked papers with an AI index.
11 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…
Quadratic Probing Revisited: Smoothed Analysis and the Fall of Robin Hood
Yang Hu, William Kuszmaul, Jingxun Liang +3
The paper studies a smoothed version of quadratic probing for hash tables, comparing Robin Hood and anti‑Robin Hood insertion orders and showing that anti‑Robin Hood achieves logar…
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…
Resizable Retrieval
William Kuszmaul, Aaron Putterman, Tingqiang Xu +2
A dynamic retrieval data structure encodes a function for a set , while supporting queries for , insertions \texttt{Insert}$…
Workload-Aware Incremental Reclustering in Cloud Data Warehouses
Yipeng Liu, Renfei Zhou, Jiaqi Yan +1
Modern cloud data warehouses store data in micro-partitions and rely on metadata (e.g., zonemaps) for efficient data pruning during query processing. Maintaining data clustering in…