Dynamic relative compression, dynamic partial sums, and substring concatenation
From MaRDI portal
Publication:1755738
DOI10.1007/s00453-017-0380-7zbMath1410.68415OpenAlexW2963238039WikidataQ60554309 ScholiaQ60554309MaRDI QIDQ1755738
Anders Roy Christiansen, Hjalte Wedel Vildhøj, Søren Vind, Philip Bille, Frederik Rye Skjoldjensen, Patrick Hagge Cording, Inge Li Gørtz
Publication date: 11 January 2019
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2016/6787/
Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Algorithms on strings (68W32)
Related Items (7)
Space-efficient B trees via load-balancing ⋮ Internal masked prefix sums and its connection to fully internal measurement queries ⋮ Random access in persistent strings and segment selection ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Partial sums on the ultra-wide word RAM ⋮ Repetition Detection in a Dynamic String
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Succinct data structures for searchable partial sums with optimal worst-case performance
- A simple storage scheme for strings achieving entropy bounds
- Bounded ordered dictionaries in O(log log N) time and O(n) space
- Preserving order in a forest in less than logarithmic time and linear space
- Surpassing the information theoretic bound with fusion trees
- String indexing for patterns with wildcards
- Fast relative Lempel-Ziv self-index for similar sequences
- Fully Functional Static and Dynamic Succinct Trees
- CRAM: Compressed Random Access Memory
- Weighted Ancestors in Suffix Trees
- Dynamic text and static pattern matching
- Space-Efficient String Indexing for Wildcard Pattern Matching.
- Relative Lempel-Ziv Compression of Genomes for Large-Scale Storage and Retrieval
- Fast Algorithms for Finding Nearest Common Ancestors
- Approximating LZ77 via Small-Space Multiple-Pattern Matching
- Indexing compressed text
- Dictionary matching and indexing with errors and don't cares
- Squeezing succinct data structures into entropy bounds
- Fast Prefix Search in Little Space, with Applications
- Data compression via textual substitution
- Design and implementation of an efficient priority queue
- New Lower Bound Techniques for Dynamic Partial Sums and Related Problems
- Examining Computational Geometry, Van Emde Boas Trees, and Hashing from the Perspective of the Fusion Tree
- Optimal Dynamic Sequence Representations
- Approximate Range Emptiness in Constant Time and Optimal Space
- The macro model for data compression (Extended Abstract)
This page was built for publication: Dynamic relative compression, dynamic partial sums, and substring concatenation
