Fully Functional Static and Dynamic Succinct Trees
From MaRDI portal
Publication:2799480
DOI10.1145/2601073zbMath1333.68084OpenAlexW2147935317MaRDI QIDQ2799480
Kunihiko Sadakane, Gonzalo Navarro
Publication date: 11 April 2016
Published in: ACM Transactions on Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/2601073
Related Items (65)
On succinct representations of binary trees ⋮ Fast construction of wavelet trees ⋮ Lyndon array construction during Burrows-Wheeler inversion ⋮ Compressed Data Structures for Dynamic Sequences ⋮ Unnamed Item ⋮ Succinct data structures for series-parallel, block-cactus and 3-leaf power graphs ⋮ Improved range minimum queries ⋮ Grammar-compressed indexes with logarithmic search time ⋮ Representation of ordered trees with a given degree distribution ⋮ Practical space-efficient index for structural pattern matching ⋮ Succinct encoding of binary strings representing triangulations ⋮ Parallel construction of succinct trees ⋮ Lempel Ziv Computation in Small Space (LZ-CISS) ⋮ Compact binary relation representations with rich functionality ⋮ Compressed dynamic range majority and minority data structures ⋮ Faster Lightweight Lempel-Ziv Parsing ⋮ Faster repetition-aware compressed suffix trees based on block trees ⋮ Compact representation of graphs with bounded bandwidth or treedepth ⋮ Compact representations of spatial hierarchical structures with support for topological queries ⋮ Ranked Document Retrieval in External Memory ⋮ Engineering Practical Lempel-Ziv Tries ⋮ Succinct data structure for dynamic trees with faster queries ⋮ Space-efficient data structure for next/previous larger/smaller value queries ⋮ Unnamed Item ⋮ Succinct data structure for path graphs ⋮ Unnamed Item ⋮ A faster implementation of online RLBWT and its application to LZ77 parsing ⋮ Wavelet trees for all ⋮ A Space-Efficient Algorithm for the Dynamic DFS Problem in Undirected Graphs ⋮ Block trees ⋮ Succinct representation of labeled trees ⋮ A framework for succinct labeled ordinal trees over large alphabets ⋮ Succinct representations for (non)deterministic finite automata ⋮ Efficient computation of spatial queries over points stored in \(k^2\)-tree compact data structures ⋮ Path queries on functions ⋮ Simple and efficient fully-functional succinct trees ⋮ Fast compressed self-indexes with deterministic linear-time construction ⋮ Dynamic relative compression, dynamic partial sums, and substring concatenation ⋮ Lempel-Ziv compressed structures for document retrieval ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Lempel-Ziv factorization powered by space efficient suffix trees ⋮ Constant-time tree traversal and subtree equality check for grammar-compressed trees ⋮ Compact representation of graphs of small clique-width ⋮ Dynamic path queries in linear space ⋮ Fast and compact planar embeddings ⋮ Ranked document selection ⋮ Unnamed Item ⋮ Compressed Multiple Pattern Matching ⋮ Unnamed Item ⋮ Constant delay traversal of grammar-compressed graphs with bounded rank ⋮ A Space-Optimal Grammar Compression. ⋮ Tree path majority data structures ⋮ Succinct representation for (non)deterministic finite automata ⋮ Faster compressed quadtrees ⋮ DenseZDD: a compact and fast index for families of sets ⋮ Navigating planar topologies in near-optimal space and time ⋮ Structural Pattern Matching - Succinctly. ⋮ Faster Compressed Suffix Trees for Repetitive Collections ⋮ Fast Compressed Self-Indexes with Deterministic Linear-Time Construction ⋮ Fast matching statistics in small space ⋮ Practical Compact Indexes for Top-kDocument Retrieval ⋮ Succinct dynamic cardinal trees
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Ultra-succinct representation of ordered trees with applications
- Succinct representation of dynamic trees
- An implicit data structure supporting insertion, deletion, and search in \(O(\log ^ 2\,n)\) time
- The level ancestor problem simplified
- Rank/select on dynamic compressed sequences and applications
- Representing trees of higher degree
- A simple optimal representation for balanced parentheses
- Succinct data structures for flexible text retrieval systems
- Surpassing the information theoretic bound with fusion trees
- Compressed suffix trees with full functionality
- Rank and select revisited and extended
- Space Efficient Suffix Trees
- Low Redundancy in Static Dictionaries with Constant Query Time
- Succinct Representation of Balanced Parentheses and Static Trees
- Wavelet Trees for All
- Succinct Representations of Binary Trees for Range Minimum Queries
- Time-space trade-offs for predecessor search
- Succinct ordinal trees with level-ancestor queries
- Compressed representations of sequences and full-text indexes
- Compressed indexes for dynamic text collections
- Succinct Dynamic Cardinal Trees with Constant Time Operations for Small Alphabet
- LRM-Trees: Compressed Indices, Adaptive Sorting, and Compressed Permutations
- Succinct indexes for strings, binary relations and multilabeled trees
- An analysis of the Burrows—Wheeler transform
- Compressing and indexing labeled trees, with applications
- An Improved Succinct Representation for Dynamic k-ary Trees
- A Uniform Approach Towards Succinct Representation of Trees
- On the Size of Succinct Indices
- Optimal Succinctness for Range Minimum Queries
- A New Succinct Representation of RMQ-Information and Improvements in the Enhanced Suffix Array
- Universal Succinct Representations of Trees?
- Breaking a Time-and-Space Barrier in Constructing Full-Text Indices
- A unifying look at data structures
- Succinct Indexable Dictionaries with Applications to Encoding $k$-ary Trees, Prefix Sums and Multisets
- A SIMPLE BALANCED SEARCH TREE WITH O(1) WORST-CASE UPDATE TIME
- Balanced parentheses strike back
- Dynamic entropy-compressed sequences and full-text indexes
- Optimal Dynamic Sequence Representations
- Engineering the LOUDS Succinct Tree Representation
- Orderly Spanning Trees with Applications
- Succinct Ordinal Trees Based on Tree Covering
- Automata, Languages and Programming
- Logarithmic Lower Bounds in the Cell-Probe Model
This page was built for publication: Fully Functional Static and Dynamic Succinct Trees
