research
∙
04/14/2023
Optimal Uncoordinated Unique IDs
In the Uncoordinated Unique Identifiers Problem (UUIDP) there are n inde...
share
research
∙
04/11/2023
An Associativity Threshold Phenomenon in Set-Associative Caches
In an α-way set-associative cache, the cache is partitioned into disjoin...
research
∙
10/08/2022
IcebergHT: High Performance PMEM Hash Tables Through Stability and Low Associativity
Modern hash table designs strive to minimize space while maximizing spee...
research
∙
07/21/2022
Tight Bounds for Monotone Minimal Perfect Hashing
The monotone minimal perfect hash function (MMPHF) problem is the follow...
research
∙
03/28/2022
GraphZeppelin: Storage-Friendly Sketching for Connected Components on Dynamic Graph Streams
Finding the connected components of a graph is a fundamental problem wit...
research
∙
03/05/2022
Online List Labeling: Breaking the log^2n Barrier
The online list labeling problem is an algorithmic primitive with a larg...
research
∙
01/05/2022
What Does Dynamic Optimality Mean in External Memory?
In this paper, we revisit the question of how the dynamic optimality of ...
research
∙
11/24/2021
Tiny Pointers
This paper introduces a new data-structural object that we call the tiny...
research
∙
10/31/2021
On the Optimal Time/Space Tradeoff for Hash Tables
For nearly six decades, the central open question in the study of hash t...
research
∙
09/09/2021
All-Purpose Hashing
Despite being one of the oldest data structures in computer science, has...
research
∙
08/16/2021
Better GPU Hash Tables
We revisit the problem of building static hash tables on the GPU and des...
research
∙
01/21/2020
Streaming Complexity of Spanning Tree Computation
The semi-streaming model is a variant of the streaming model frequently ...
research
∙
04/05/2019
Achieving Optimal Backlog in Multi-Processor Cup Games
The single- and multi- processor cup games can be used to model natural ...
research
∙
12/24/2018
The Online Event-Detection Problem
Given a stream S = (s_1, s_2, ..., s_N), a ϕ-heavy hitter is an item s_i...
research
∙
09/30/2018
Streaming Algorithms for Planar Convex Hulls
Many classical algorithms are known for computing the convex hull of a s...
research
∙
07/04/2018
Optimal Ball Recycling
Balls-and-bins games have been a wildly successful tool for modeling loa...
research
∙
05/23/2018
Optimal Hashing in External Memory
Hash tables are a ubiquitous class of dictionary data structures. Howeve...
research
∙
03/13/2018
Closure Operators and Spam Resistance for PageRank
We study the spammablility of ranking functions on the web. Although gra...
research
∙
11/05/2017
Bloom Filters, Adaptivity, and the Dictionary Problem
The Bloom filter---or, more generally, an approximate membership query d...
research
∙
10/30/2017
A Dynamic Hash Table for the GPU
We design and implement a fully concurrent dynamic hash table for GPUs w...
research
∙
08/01/2012