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.
Funding Information
  • Ministero dell’Istruzione, dell’Università e della Ricerca (20229BCXNW)
  • European Commission (882500)

This publication has 29 references indexed in Scilit: