Faster Wavelet Tree Queries
- 3 September 2025
- journal article
- Published by Wiley in Software: Practice and Experience
- Vol. 55 (12) , 1931-1946
Abstract
Introduction: Given a text, rank and select queries return the number of occurrences of a character up to a position (rank) or the position of a character with a given rank (select). These queries have applications in compression, computational geometry, and most notably pattern matching in the form of the backward search, which is the backbone of many compressed full‐text indices. Currently, in practice, for text over non‐binary alphabets, the wavelet tree is probably the most used data structure for rank and select queries. Objective: The goal of this work is to design techniques that accelerate rank, select, and access queries while retaining the space efficiency of both uncompressed and compressed representations. Methods: To this end, we change the underlying tree structure from a binary tree to a quaternary tree and reduce cache misses by approximating rank queries using a predictive model to prefetch all data required for the actual rank query. Finally, we also extend our approach to Huffman‐shaped wavelet trees. Result: Our methods allowed us to achieve speedups of up to a factor of two for access and select queries and up to three for rank queries compared to the SDSL implementation. With Huffman‐shaped wavelet trees, we achieved up to three times faster access and select, and 3.8 times faster rank. In addition, our approach still achieves a reduction of space usage by up to 30% for compressible datasets. Conclusion: By changing the tree structure and using predictive prefetching, we obtain a data structure that substantially outperforms other standard wavelet tree implementations, delivering significantly faster query performance while also occupying compact space.Keywords
Funding Information
- Ministero dell’Istruzione, dell’Università e della Ricerca (20229BCXNW)
- European Commission (882500)
This publication has 29 references indexed in Scilit:
- Engineering Compact Data Structures for Rank and Select Queries on Bit Vectors2022
- Rank/select queries over mutable bitmapsInformation Systems, 2021
- Block treesJournal of Computer and System Sciences, 2021
- Improved parallel construction of wavelet trees and rank/select structuresInformation and Computation, 2020
- Parallel External Memory Wavelet Tree and Wavelet Matrix Construction2019
- Fixed Block Compression Boosting in FM-Indexes: Theory and PracticeAlgorithmica, 2018
- Parallel construction of wavelet trees on multicore architecturesKnowledge and Information Systems, 2016
- The wavelet matrix: An efficient wavelet tree for large alphabetsInformation Systems, 2015
- Space-Efficient Substring Occurrence EstimationAlgorithmica, 2014
- The myriad virtues of Wavelet TreesInformation and Computation, 2009