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 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 …

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 propose new succinct representations of ordinal trees, which have been studied
extensively. It is known that any n-node static tree can be represented in 2 n+ o (n) bits and a …

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 …

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 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 …

Current data structures for searching large string collections either fail to achieve minimum
space or cause too many cache misses. In this paper we discuss some edge linearizations …