Fast construction of wavelet trees

DOI10.1016/J.TCS.2015.11.011MaRDI QIDQ294942zbMATH OpenOpenAlexFDO

Authors J. Ian Munro, Yakov Nekrich, 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

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

Recommendations

• Fast wavelet tree construction in practice
• On wavelet tree construction
• Online construction of wavelet trees
• Practical Wavelet Tree Construction
• Wavelet trees meet suffix trees

Cites work

• scientific article; zbMATH DE number 2079421 (Why is no real title available?)
• scientific article; zbMATH DE number 6297698 (Why is no real title available?)
• A Functional Approach to Data Structures and Its Use in Multidimensional Searching
• Compressed representations of permutations, and applications
• Compressed representations of sequences and full-text indexes
• Compressing and indexing labeled trees, with applications
• Dynamic Rank-Select Structures with Applications to Run-Length Encoded Texts
• Dynamic entropy-compressed sequences and full-text indexes
• Dynamic rank/select structures with applications to run-length encoded texts
• Extended compact web graph representations
• Fully functional static and dynamic succinct trees
• Improved Dynamic Rank-Select Entropy-Bound Structures
• New algorithms on wavelet trees and applications to information retrieval
• On wavelet tree construction
• Optimal planar orthogonal skyline counting queries
• Orthogonal range searching on the RAM, revisited
• Rank/select on dynamic compressed sequences and applications
• Sorted range reporting
• Space-Efficient Algorithms for Document Retrieval
• Space-efficient data-analysis queries on grids
• Succinct Indexable Dictionaries with Applications to Encoding $k$-ary Trees, Prefix Sums and Multisets
• Succinct indexes for strings, binary relations and multi-labeled trees
• Wavelet trees for all
• Wavelet trees meet suffix trees

Cited in

(17)

• Internal pattern matching queries in a text and applications
• Internal dictionary matching
• Online construction of wavelet trees
• Fast wavelet tree construction in practice
• Space-efficient fully dynamic DFS in undirected graphs
• A Space-Efficient Algorithm for the Dynamic DFS Problem in Undirected Graphs
• Accelerated partial decoding in wavelet trees
• Algorithms to compute the Burrows-Wheeler similarity distribution
• Parallel external memory wavelet tree and wavelet matrix construction
• The ring: worst-case optimal joins in graph databases using (almost) no extra space
• Wavelet trees meet suffix trees
• scientific article; zbMATH DE number 7651193 (Why is no real title available?)
• Practical Wavelet Tree Construction
• Simple, Fast and Lightweight Parallel Wavelet Tree Construction
• Parallel lightweight wavelet tree, suffix array and FM-index construction
• On wavelet tree construction
• Efficient indexes for jumbled pattern matching with constant-sized alphabet

This page was built for publication: Fast construction of wavelet trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q294942)