Compressing and indexing labeled trees, with applications
From MaRDI portal
Publication:3455566
DOI10.1145/1613676.1613680zbMath1326.68132OpenAlexW2018866650MaRDI 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 transformXML indexingXML compressionpath searchinglabeled tree compressionlabeled tree indexingtree navigation
Searching and sorting (68P10) Database theory (68P15) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Data structures (68P05)
Related Items (34)
Graphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless SETH fails ⋮ Fast construction of wavelet trees ⋮ Constructing small tree grammars and small circuits for formulas ⋮ Grammar compressed sequences with rank/select support ⋮ Wheeler graphs: a framework for BWT-based data structures ⋮ Space efficient data structures for dynamic orthogonal range counting ⋮ Compressed string dictionaries via data-aware subtrie compaction ⋮ On the hardness of computing the edit distance of shallow trees ⋮ Ultra-succinct representation of ordered trees with applications ⋮ Computational graph pangenomics: a tutorial on data structures and their applications ⋮ Unnamed Item ⋮ FM-index of alignment with gaps ⋮ Succinct data structures for nearest colored node in a tree ⋮ Efficient fully-compressed sequence representations ⋮ Optimal indexes for sparse bit vectors ⋮ Succinct representation of labeled trees ⋮ Graphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless SETH fails ⋮ A framework for succinct labeled ordinal trees over large alphabets ⋮ Tree compression using string grammars ⋮ Computing the multi-string BWT and LCP array in external memory ⋮ Forty Years of Text Indexing ⋮ Unnamed Item ⋮ Fully Functional Static and Dynamic Succinct Trees ⋮ On the Hardness and Inapproximability of Recognizing Wheeler Graphs ⋮ Lightweight merging of compressed indices based on BWT variants ⋮ Fast Compressed Tries through Path Decompositions ⋮ Succinct Representations of Ordinal Trees ⋮ Random Access to Grammar-Compressed Strings and Trees ⋮ Constructing LZ78 tries and position heaps in linear time for large alphabets ⋮ Tree compression with top trees ⋮ Slowing Down Top Trees for Better Worst-Case Compression ⋮ Space efficient merging of de Bruijn graphs and Wheeler graphs ⋮ On the complexity of recognizing Wheeler graphs ⋮ Succinct dynamic cardinal trees
This page was built for publication: Compressing and indexing labeled trees, with applications
