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 …

A repetitive sequence collection is a set of sequences which are small variations of each
other. A prominent example are genome sequences of individuals of the same or close …

We present a practical study on the compact representation of sequences supporting rank,
select, and access queries. While there are several theoretical solutions to the problem, only …

Wavelet trees are widely used in the representation of sequences, permutations, text
collections, binary relations, discrete points, and other succinct data structures. We show …

The wavelet tree is a flexible data structure that permits representing sequences S [1, n] of
symbols over an alphabet of size σ, within compressed space and supporting a wide range …

Recent advances in biotechnology and web technology are continuously generating huge
collections of similar strings. People now face the problem of storing them compactly while …

The Permuterm index [Garfield 1976] is a time-efficient and elegant solution to the string
dictionary problem in which pattern queries may possibly include one wild-card symbol …

Colored range queries are a well-studied topic in computational geometry and database
research that, in the past decade, have found exciting applications in information retrieval. In …

Wavelet Trees have been introduced by Grossi et al. in SODA 2003 and have been rapidly
recognized as a very flexible tool for the design of compressed full-text indexes and data …

The FM index (Ferragina and Manzini in J ACM 52 (4): 552–581, 2005) is a widely-used
compressed data structure that stores a string T in a compressed form and also supports fast …