|Title:||Analysis and Comparison of Rank Queries|
Department of Computer Science, University of British Columbia
Succinct full-text indexes provide fast substring search over large text collections and recently in bioinformatics, such indexes have been used to meet the increasing performance demands when it comes to sequence analysis. Two essential building blocks of these indexes are the functions rank (counting the number of ones up to a given position) and select (find the position of the i-th bit set). In this talk, we will examine rank in detail, analyzing and comparing the basic 32-bit solution to a novel 64-bit broadword programming solution recently proposed by Sebastiano Vigna, which consumes less space and is significantly faster than current state-of-the-art 32-bit implementations.