Dynamic relative compression, dynamic partial sums, and substring concatenation
type: Item
instance of: scholarly article
title: Dynamic relative compression, dynamic partial sums, and substring concatenation
zbMATH Open document ID: 1410.68415
author: Philip Bille
author: Anders Roy Christiansen
author: Patrick Hagge Cording
author: Inge Li Gørtz
author: Frederik Rye Skjoldjensen
author: Hjalte Wedel Vildhøj
author: Søren Vind
published in: Algorithmica
publication date: 2019-01-11T00:00:00Z
full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2016/6787/
Mathematics Subject Classification ID: 68W32
Mathematics Subject Classification ID: 68P30
zbMATH DE Number: 7000140
MaRDI profile type: Publication
OpenAlex ID: W2963238039
Wikidata QID: Q60554309
cites work: Q4952706
cites work: Dynamic text and static pattern matching
cites work: Fast Prefix Search in Little Space, with Applications
cites work: String indexing for patterns with wildcards
cites work: Dictionary matching and indexing with errors and don't cares
cites work: Q4028873
cites work: Fast relative Lempel-Ziv self-index for similar sequences
cites work: Indexing compressed text
cites work: A simple storage scheme for strings achieving entropy bounds
cites work: Approximating LZ77 via Small-Space Multiple-Pattern Matching
cites work: Surpassing the information theoretic bound with fusion trees
cites work: Weighted Ancestors in Suffix Trees
cites work: Approximate Range Emptiness in Constant Time and Optimal Space
cites work: Q4471381
cites work: Fast Algorithms for Finding Nearest Common Ancestors
cites work: Succinct data structures for searchable partial sums with optimal worst-case performance
cites work: New Lower Bound Techniques for Dynamic Partial Sums and Related Problems
cites work: Q3129920
cites work: CRAM: Compressed Random Access Memory
cites work: Q3996398
cites work: Relative Lempel-Ziv Compression of Genomes for Large-Scale Storage and Retrieval
cites work: Space-Efficient String Indexing for Wildcard Pattern Matching.
cites work: Bounded ordered dictionaries in O(log log N) time and O(n) space
cites work: Optimal Dynamic Sequence Representations
cites work: Fully functional static and dynamic succinct trees
cites work: Q5501238
cites work: Q4778577
cites work: Squeezing succinct data structures into entropy bounds
cites work: The macro model for data compression (Extended Abstract)
cites work: Data compression via textual substitution
cites work: Q3992915
cites work: Preserving order in a forest in less than logarithmic time and linear space
cites work: Design and implementation of an efficient priority queue
cites work: Examining Computational Geometry, Van Emde Boas Trees, and Hashing from the Perspective of the Fusion Tree
DOI: 10.1007/S00453-017-0380-7
description: scientific article; zbMATH DE number 7000140