• bit vectors
• quad vectors
• Wavelet matrices
• Wavelet trees

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.