License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2020.48
URN: urn:nbn:de:0030-drops-133922
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/13392/
Go to the corresponding LIPIcs Volume Portal

Bille, Philip ; Gørtz, Inge Li

Random Access in Persistent Strings

pdf-format:
LIPIcs-ISAAC-2020-48.pdf (3 MB)

Abstract

We consider compact representations of collections of similar strings that support random access queries. The collection of strings is given by a rooted tree where edges are labeled by an edit operation (inserting, deleting, or replacing a character) and a node represents the string obtained by applying the sequence of edit operations on the path from the root to the node. The goal is to compactly represent the entire collection while supporting fast random access to any part of a string in the collection. This problem captures natural scenarios such as representing the past history of an edited document or representing highly-repetitive collections. Given a tree with n nodes, we show how to represent the corresponding collection in O(n) space and optimal O(log n/ log log n) query time. This improves the previous time-space trade-offs for the problem. To obtain our results, we introduce new techniques and ideas, including a reduction to a new geometric line segment selection together with an efficient solution.

BibTeX - Entry

@InProceedings{bille_et_al:LIPIcs:2020:13392,
  author =	{Philip Bille and Inge Li G{\o}rtz},
  title =	{{Random Access in Persistent Strings}},
  booktitle =	{31st International Symposium on Algorithms and Computation (ISAAC 2020)},
  pages =	{48:1--48:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-173-3},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{181},
  editor =	{Yixin Cao and Siu-Wing Cheng and Minming Li},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/13392},
  URN =		{urn:nbn:de:0030-drops-133922},
  doi =		{10.4230/LIPIcs.ISAAC.2020.48},
  annote =	{Keywords: Data compression, data structures, persistent strings}
}

Keywords: Data compression, data structures, persistent strings
Collection: 31st International Symposium on Algorithms and Computation (ISAAC 2020)
Issue Date: 2020
Date of publication: 04.12.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI