Dynamic relative compression, dynamic partial sums, and substring concatenation

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/

Mathematics Subject Classification ID

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