Compressing and indexing labeled trees, with applications
From MaRDI portal
Publication:3455566
DOI10.1145/1613676.1613680zbMath1326.68132MaRDI QIDQ3455566
No author found.
Publication date: 7 December 2015
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1613676.1613680
Burrows-Wheeler transform; XML indexing; XML compression; path searching; labeled tree compression; labeled tree indexing; tree navigation
68P10: Searching and sorting
68P15: Database theory
68P30: Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science)
68P05: Data structures
Related Items
Unnamed Item, Forty Years of Text Indexing, Unnamed Item, On the Hardness and Inapproximability of Recognizing Wheeler Graphs, Random Access to Grammar-Compressed Strings and Trees, Slowing Down Top Trees for Better Worst-Case Compression, Graphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless SETH fails, Compressed string dictionaries via data-aware subtrie compaction, On the hardness of computing the edit distance of shallow trees, Succinct dynamic cardinal trees, Fast construction of wavelet trees, Space efficient data structures for dynamic orthogonal range counting, Ultra-succinct representation of ordered trees with applications, Efficient fully-compressed sequence representations, Optimal indexes for sparse bit vectors, Succinct representation of labeled trees, A framework for succinct labeled ordinal trees over large alphabets, Graphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless SETH fails, Wheeler graphs: a framework for BWT-based data structures, FM-index of alignment with gaps, Succinct data structures for nearest colored node in a tree, Tree compression using string grammars, Computing the multi-string BWT and LCP array in external memory, Space efficient merging of de Bruijn graphs and Wheeler graphs, On the complexity of recognizing Wheeler graphs, Lightweight merging of compressed indices based on BWT variants, Constructing LZ78 tries and position heaps in linear time for large alphabets, Tree compression with top trees, Constructing small tree grammars and small circuits for formulas, Grammar compressed sequences with rank/select support, Fully Functional Static and Dynamic Succinct Trees, Fast Compressed Tries through Path Decompositions, Succinct Representations of Ordinal Trees