Faster Wavelet Tree Queries
Fuente:
Wiley Open Access
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Artículo Open Access |
| Veröffentlicht: |
Wiley
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1867008538887323648 |
|---|---|
| author | Florian Kurpicz Angelo Savino Rossano Venturini |
| author_facet | Florian Kurpicz Angelo Savino Rossano Venturini Florian Kurpicz Angelo Savino Rossano Venturini |
| collection | Wiley Open Access |
| contents | Faster Wavelet Tree Queries Florian Kurpicz Angelo Savino Rossano Venturini Software: Practice and Experience 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. 10.1002/spe.70013 http://onlinelibrary.wiley.com/termsAndConditions#vor |
| doi_str_mv | 10.1002/spe.70013 |
| format | Artículo Open Access |
| id | wiley_oa_10_1002_spe_70013 |
| institution | Wiley Open Access |
| license_str_mv | http://onlinelibrary.wiley.com/termsAndConditions#vor |
| publishDate | 2025 |
| publisher | Wiley |
| record_format | wiley_oa |
| spellingShingle | Faster Wavelet Tree Queries Florian Kurpicz Angelo Savino Rossano Venturini Software: Practice and Experience Faster Wavelet Tree Queries Florian Kurpicz Angelo Savino Rossano Venturini Software: Practice and Experience 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. 10.1002/spe.70013 http://onlinelibrary.wiley.com/termsAndConditions#vor |
| title | Faster Wavelet Tree Queries |
| topic | Software: Practice and Experience |
| url | https://onlinelibrary.wiley.com/doi/10.1002/spe.70013 |