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.