Wavelet trees: A survey
Open Access
- 1 January 2012
- journal article
- research article
- Published by National Library of Serbia in Computer Science and Information Systems
- Vol. 9 (2) , 585-625
Abstract
The topic of this paper is the exploration of the various characteristics of the wavelet tree data structure, a data structure that was initially proposed for text compression applications but has found a plethora of other uses in text indexing and retrieval. Issues concerning the efficient maintenance of the structure, plus its handling in various applications are explored. Our main aim is to provide to computer science researchers that would like to explore the specific area, an up-to-date comprehensive material covering a wide range of applications. This kind of up-to-date survey is missing from the current bibliography and we hope that it will help young researchers to get familiar with the notions of this research area.Keywords
This publication has 22 references indexed in Scilit:
- Space-efficient construction of Lempel–Ziv compressed text indexesInformation and Computation, 2011
- Improved data structures for the orthogonal range successor problemComputational Geometry, 2011
- Efficient index for retrieving top-k most frequent documentsJournal of Discrete Algorithms, 2010
- Dynamic rank/select structures with applications to run-length encoded textsTheoretical Computer Science, 2009
- The myriad virtues of Wavelet TreesInformation and Computation, 2009
- Rank and Select for Succinct Data StructuresElectronic Notes in Theoretical Computer Science, 2009
- Output-sensitive autocompletion searchInformation Retrieval Journal, 2008
- The affix array data structure and its applications to RNA secondary structure analysisTheoretical Computer Science, 2007
- Adaptive searching in succinctly encoded binary relations and tree-structured documentsTheoretical Computer Science, 2007
- Rank and select revisited and extendedTheoretical Computer Science, 2007