In the range α-majority query problem, we preprocess a given sequence S[1.n] for a fixed threshold α ϵ (0, 1], such that given a query range [i.j], the symbols that occur more than α (j-i+1) times in S[i.j] can be reported ...

The need to store and query a set of strings - a string dictionary - arises in many kinds of applications. While classically these string dictionaries have accounted for a small share of the total space budget (e.g., in ...

In an effort to calibrate assessment methods of existing earth structures, a new database with compression and bending tests on unbaked earth specimens was assembled. The data-collection database includes 2670 tests with ...

Compressed representations have become effective to store and access largeWeb and social graphs, in order to support various graph querying and mining tasks. The existing representations exploit various typical patterns ...

The Block Tree (BT) is a novel compact data structure designed to compress sequence collections. It obtains compression ratios close to Lempel-Ziv and supports efficient direct access to any substring. The BT divides the ...

We present a data structure that stores a sequence s[1..n] over alphabet [1..σ ] in nH0(s) + o(n)(H0(s)+1) bits, where H0(s) is the zero-order entropy of s. This structure supports the queries access, rank and select, ...

Full-text indexes provide fast substring search over large text collections. A serious problem of these indexes has traditionally been their space consumption. A recent trend is to develop indexes that exploit the ...

Suffix trees are one of the most versatile data structures in stringology, with many applications in bioinformatics. Their main drawback is their size, which can be tens of times larger than the input sequence. Much effort ...