Wavelet Trees for All
Gonzalo Navarro
The wavelet tree is a versatile data structure that serves a number of
purposes, from string processing to geometry and more. It can be regarded as a
device that represents a sequence, a reordering, or a grid of points.
In addition, its space adapts to various entropy measures of the data it
encodes,
enabling compressed representations. New competitive solutions to a number of
problems, based on wavelet trees, are appearing every year. In this survey we
give an overview of the surprising number of applications in which we have
found wavelet trees useful: basic and weighted point grids,
sets of rectangles, strings, permutations, binary relations, graphs, inverted
indexes, document retrieval indexes, full-text indexes, XML indexes, and
general numeric sequences.