A dictionary data structure maintains a set of at most n keys from the universe U under key
insertions and deletions, such that given a query x∈U, it returns if x is in the set. Some …

A data structure is said to be strongly history independent if its state is fully determined by its
current set of elements (and random bits). One of the most basic questions that strongly …

This paper introduces a new data-structural object that we call the tiny pointer. In many
applications, traditional log n-bit pointers can be replaced with o (log n)-bit tiny pointers at …

This paper considers the basic question of how strong of a probabilistic guarantee can a
hash table, storing n(1+Θ(1))\logn-bit key/value pairs, offer? Past work on this question has …

Augmented B-trees (aB-trees) are a broad class of data structures. The seminal work
“succincter” by Pǎtraşcu 1 showed that any aB-tree can be stored using only two bits of …

In the 2-choice allocation problem, m balls are placed into n bins, and each ball must
choose between two random bins i,j∈n that it has been assigned to. It has been known for …

Modern work on hashing has led to hash tables with extraordinary guarantees. However,
these data structures are too complex to be taught in (even an advanced) data structures …

Dictionaries have been one of the central questions in data structures. A dictionary data
structure maintains a set of key-value pairs under insertions and deletions such that given a …

A filter is a data structure that answers approximate-membership queries on a set S of n
elements, with a false-positive rate of є. A filter is said to be dynamic if it supports …

We introduce a classical open-addressed hash table, called rainbow hashing, that supports
a load factor of up to 1 -ε, while also supporting O(1) expected-time queries, and …