The Wavelet Matrix
Francisco Claude and Gonzalo Navarro
The wavelet tree (Grossi et al., SODA 2003) is nowadays a popular
succinct data structure for text indexes, discrete grids, and many other
applications. When it has many nodes, a levelwise representation proposed
by Mäkinen and Navarro (LATIN 2006) is preferable.
We propose a different arrangement of the levelwise data,
so that the bitmaps are shuffled in a different way. The result can
no more be called a wavelet tree, and we dub it wavelet matrix.
We demonstrate that the wavelet matrix is simpler to build, simpler to
query, and faster in practice than the levelwise wavelet tree.
This has a direct impact on many applications that use the levelwise
wavelet tree for different purposes.