Document retrieval is one of the best-established information retrieval activities since
the'60s, pervading all search engines. Its aim is to obtain, from a collection of text …

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 …

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 …

Self-indexes are able to represent a text asymptotically within the information-theoretic lower
bound under the k th order entropy model and offer access to any text substring and indexed …

We introduce the first grammar-compressed representation of a sequence that supports
searches in time that depends only logarithmically on the size of the grammar. Given a text T …

We describe a data structure that supports access, rank, and select queries, as well as
symbol insertions and deletions, on a string S 1, n over alphabet 1..σ in time …

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 …

Abstract In Geographic Information Systems (GIS) the attributes of the space (altitude,
temperature, etc.) are usually represented using a raster model. There are no compact …

We introduce a new approach to LZ77 factorization that uses \O(n/d) words of working space
and \O(dn) time for any d≥ 1 (for polylogarithmic alphabet sizes). We also describe carefully …

We prove that, given a permutation π over [1.. n] formed of nRuns sorted blocks of sizes
given by the vector R=< r 1,…, r nRuns>, there exists a compressed data structure encoding …