Faster Wavelet Tree Queries
Preprint
Abstract
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, e.g., compression, computational geometry, and most notably pattern matching in the form of the backward search -- 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. In this paper, we present techniques to speed up queries by a factor of two (access and select) up to three (rank), compared to the wavelet tree implementation contained in the widely used Succinct Data Structure Library (SDSL). To this end, we change the underlying tree structure from a binary tree to a 4-ary tree and reduce cache misses by approximating rank queries using a predictive model to prefetch all data required for the actual rank query.Keywords
All Related Versions
This publication has 37 references indexed in Scilit:
- Engineering Compact Data Structures for Rank and Select Queries on Bit Vectors2022
- Fast Wavelet Tree Construction in Practice2018
- Fixed Block Compression Boosting in FM-Indexes: Theory and PracticeAlgorithmica, 2018
- Access, Rank, and Select in Grammar-compressed Strings2015
- Space-Efficient Substring Occurrence EstimationAlgorithmica, 2014
- From Theory to Practice: Plug and Play with Succinct Data Structures2014
- Space-Efficient, High-Performance Rank and Select Structures on Uncompressed Bit SequencesLecture Notes in Computer Science, 2013
- Fast, Small, Simple Rank/Select on Bitmaps2012
- Broadword Implementation of Rank/Select Queries2008
- Efficient Implementation of Rank and Select Functions for Succinct RepresentationLecture Notes in Computer Science, 2005