Tipo di tesi
Tesi di laurea magistrale
Titolo
Faster Wavelet Trees with Quad Vectors
Corso di studi
INFORMATICA
Parole chiave
- bit vectors
- quad vectors
- Wavelet matrices
- Wavelet trees
Data inizio appello
24/02/2023
Consultabilità
Non consultabile
Data di rilascio
24/02/2063
Riassunto (Italiano)
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 find application in compression, computational geometry, pattern matching, and are the basic building blocks of compressed full-text indexes. A Wavelet tree is a compact data structure that, for a text of length 'n' over an alphabet of size 'sigma', can answer rank and select queries in O(log 'sigma') time.
In this thesis, we show how to improve the latency of queries in Wavelet trees by using a 4-ary tree instead of a binary tree as the layout of the Wavelet tree. To this end, we present a space-efficient rank and select data structure for quad vectors.Query latency is an important measure when queries depend on others.
