Wavelet Trees for All
Gonzalo Navarro
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 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 wavelet trees and the surprising number of applications
in which we have found them 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.