License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICDT.2023.7
URN: urn:nbn:de:0030-drops-177495
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/17749/
Muñoz, Martín ;
Riveros, Cristian
Constant-Delay Enumeration for SLP-Compressed Documents
Abstract
We study the problem of enumerating results from a query over a compressed document. The model we use for compression are straight-line programs (SLPs), which are defined by a context-free grammar that produces a single string. For our queries we use a model called Annotated Automata, an extension of regular automata that allows annotations on letters. This model extends the notion of Regular Spanners as it allows arbitrarily long outputs. Our main result is an algorithm which evaluates such a query by enumerating all results with output-linear delay after a preprocessing phase which takes linear time on the size of the SLP, and cubic time over the size of the automaton. This is an improvement over Schmid and Schweikardt’s result [Markus L. Schmid and Nicole Schweikardt, 2021], which, with the same preprocessing time, enumerates with a delay which is logarithmic on the size of the uncompressed document. We achieve this through a persistent data structure named Enumerable Compact Sets with Shifts which guarantees output-linear delay under certain restrictions. These results imply constant-delay enumeration algorithms in the context of regular spanners. Further, we use an extension of annotated automata which utilizes succinctly encoded annotations to save an exponential factor from previous results that dealt with constant-delay enumeration over vset automata. Lastly, we extend our results in the same fashion Schmid and Schweikardt did [Markus L. Schmid and Nicole Schweikardt, 2022] to allow complex document editing while maintaining the constant-delay guarantee.
BibTeX - Entry
@InProceedings{munoz_et_al:LIPIcs.ICDT.2023.7,
author = {Mu\~{n}oz, Mart{\'\i}n and Riveros, Cristian},
title = {{Constant-Delay Enumeration for SLP-Compressed Documents}},
booktitle = {26th International Conference on Database Theory (ICDT 2023)},
pages = {7:1--7:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-270-9},
ISSN = {1868-8969},
year = {2023},
volume = {255},
editor = {Geerts, Floris and Vandevoort, Brecht},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/17749},
URN = {urn:nbn:de:0030-drops-177495},
doi = {10.4230/LIPIcs.ICDT.2023.7},
annote = {Keywords: SLP compression, query evaluation, enumeration algorithms}
}
|
Keywords: |
|
SLP compression, query evaluation, enumeration algorithms |
|
Collection: |
|
26th International Conference on Database Theory (ICDT 2023) |
|
Issue Date: |
|
2023 |
|
Date of publication: |
|
17.03.2023 |
