Although there are many advanced and specialized texts and handbooks on algorithms,
until now there was no book that focused exclusively on the wide variety of data structures …

We develop succinct data structures to represent (i) a sequence of values to support partial
sum and select queries and update (changing values) and (ii) a dynamic array consisting of …

We consider space-efficient solutions to two dynamic data structuring problems. We first give
a representation of a set S ⊆ U=\left {0,..., m-1\right\},\left| S\right|= n that supports …

Research on space efficient graph algorithms, particularly for st-connectivity, has a long
history including the celebrated polynomial time, O (lg n) bits 1 algorithm in undirected …

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 …

We introduce a new updatable representation of binary trees. The structure requires the
information theoretic minimum 2n+ o (n) bits and supports basic navigational operations in …

Recent work by Elmasry et al.(STACS 2015) and Asano et al.(ISAAC 2014), reconsidered
classical fundamental graph algorithms focusing on improving the space complexity …

A data-graph computation—popularized by such programming systems as Galois, Pregel,
GraphLab, PowerGraph, and GraphChi—is an algorithm that performs local updates on the …

The theory of arrays, introduced by McCarthy in his seminal paper “Towards a mathematical
science of computation,” is central to Computer Science. Unfortunately, the theory alone is …