Fast construction of wavelet trees

DOI10.1016/j.tcs.2015.11.011zbMath1344.68060OpenAlexW2183729464MaRDI QIDQ294942

Yakov Nekrich, J. Ian Munro, Jeffrey Scott Vitter

Publication date: 16 June 2016

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2015.11.011

zbMATH Keywords

compressed data structurescompressed sequenceswavelet trees

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Data structures (68P05)

Related Items

Parallel lightweight wavelet tree, suffix array and FM-index construction, Practical Wavelet Tree Construction, Algorithms to compute the Burrows-Wheeler similarity distribution, Unnamed Item, A Space-Efficient Algorithm for the Dynamic DFS Problem in Undirected Graphs, Efficient indexes for jumbled pattern matching with constant-sized alphabet, Internal dictionary matching, Space-efficient fully dynamic DFS in undirected graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Space-efficient data-analysis queries on grids
• New algorithms on wavelet trees and applications to information retrieval
• Dynamic rank/select structures with applications to run-length encoded texts
• Rank/select on dynamic compressed sequences and applications
• Wavelet trees for all
• Fully Functional Static and Dynamic Succinct Trees
• Sorted Range Reporting
• Compressed representations of sequences and full-text indexes
• On Wavelet Tree Construction
• Optimal Planar Orthogonal Skyline Counting Queries
• Compressing and indexing labeled trees, with applications
• Dynamic Rank-Select Structures with Applications to Run-Length Encoded Texts
• Space-Efficient Algorithms for Document Retrieval
• Extended Compact Web Graph Representations
• A Functional Approach to Data Structures and Its Use in Multidimensional Searching
• Succinct Indexable Dictionaries with Applications to Encoding $k$-ary Trees, Prefix Sums and Multisets
• Dynamic entropy-compressed sequences and full-text indexes
• Wavelet Trees Meet Suffix Trees
• COMPRESSED REPRESENTATIONS OF PERMUTATIONS, AND APPLICATIONS
• Orthogonal range searching on the RAM, revisited
• Improved Dynamic Rank-Select Entropy-Bound Structures