New Algorithms on Wavelet Trees and Applications to Information Retrieval
Travis Gagie, Gonzalo Navarro, and Simon Puglisi
Wavelet trees are widely used in the representation of sequences, permutations,
text collections, binary relations, discrete points, and other succinct data
structures. We show, however, that this still falls short of exploiting all of
the virtues of this versatile data structure. In particular we show how to
use wavelet trees to solve fundamental algorithmic problems such as
range quantile queries, range next value queries, and range
intersection queries. We explore several applications of these queries in
Information Retrieval, in particular document retrieval in
hierarchical and temporal documents, and in the representation of
inverted lists.