We propose new succinct representations of ordinal trees and match various space/time
lower bounds. It is known that any n-node static tree can be represented in 2 n+ o (n) bits so …

The wavelet tree is a versatile data structure that serves a number of purposes, from string
processing to computational geometry. It can be regarded as a device that represents a …

We can represent an array of n values from {0, 1, 2} using ceil (n log_2 3) bits (arithmetic
coding), but then we cannot retrieve a single element efficiently. Instead, we can encode …

We implement and compare the major current techniques for representing general trees in
succinct form. This is important because a general tree of n nodes is usually represented in …

We show that the compressed suffix array and the compressed suffix tree for a string of
length n over an integer alphabet of size σ≤ n can both be built in O (n)(randomized) time …

We describe a simple, but powerful local encoding technique, implying two surprising
results: 1. We show how to represent a vector of n values from some alphabet S using …

The partial sums problem in succinct data structures asks to preprocess an array A [1‥ n] of
bits into a data structure using as close to n bits as possible, and answer queries of the form …

We present a data structure that stores a sequence s 1.. n over alphabet 1.. σ in
nH_0(s)+o(n)(H_0(s)+1) bits, where H_0(s) is the zero-order entropy of s. This structure …

The topic of this paper is the exploration of the various characteristics of the wavelet tree
data structure, a data structure that was initially proposed for text compression applications …

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 …