View publication
| Title | The Wavelet Matrix |
| Authors | Francisco Claude, Gonzalo Navarro |
| Publication date | 2012 |
| Abstract | 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 Makinen 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. |
| Downloaded | 6 times |
| Pages | 167-179 |
| Conference name | International Symposium on String Processing and Information Retrieval |
| Publisher | Springer-Verlag (Berlin/Heidelberg, Germany) |
|
|
| Reference URL |
|