Dynamic Relative Compression, Dynamic Partial Sums, and Substring Concatenation

Publication: Research - peer-reviewArticle in proceedings – Annual report year: 2016

Documents

DOI

View graph of relations

Given a static reference string R and a source string S, a relative compression of S with respect to R is an encoding of S as a sequence of references to substrings of R. Relative compression schemes are a classic model of compression and have recently proved very successful for compressing highly-repetitive massive data sets such as genomes and web-data. We initiate the study of relative compression in a dynamic setting where the compressed source string S is subject to edit operations. The goal is to maintain the compressed representation compactly, while supporting edits and allowing efficient random access to the (uncompressed) source string. We present new data structures that achieve optimal time for updates and queries while using space linear in the size of the optimal relative compression, for nearly all combinations of parameters. We also present solutions for restricted and extended sets of updates. To achieve these results, we revisit the dynamic partial sums problem and the substring concatenation problem. We present new optimal or near optimal bounds for these problems. Plugging in our new results we also immediately obtain new bounds for the string indexing for patterns with wildcards problem and the dynamic text and static pattern matching problem.
Original languageEnglish
Title of host publicationProceedings of the 27th International Symposium on Algorithms and Computation (ISAAC 2016)
Number of pages13
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Publication date2016
Article number18
ISBN (print)978-3-95977-026-2
DOIs
StatePublished - 2016
Event27th International Symposium on Algorithms and Computation - Sydney, Australia

Conference

Conference27th International Symposium on Algorithms and Computation
Number27
CountryAustralia
CitySydney
Period12/12/201614/12/2016
Internet address
SeriesLeibniz International Proceedings in Informatics
Volume64
ISSN1868-8969
CitationsWeb of Science® Times Cited: No match on DOI

    Keywords

  • Relative compression, Dynamic compression, Dynamic partial sum, Sub-string concatenation, External macro compression
Download as:
Download as PDF
Select render style:
APAAuthorCBE/CSEHarvardMLAStandardVancouverShortLong
PDF
Download as HTML
Select render style:
APAAuthorCBE/CSEHarvardMLAStandardVancouverShortLong
HTML
Download as Word
Select render style:
APAAuthorCBE/CSEHarvardMLAStandardVancouverShortLong
Word

Download statistics

No data available

ID: 128073341