DROPS

Document

DOI: 10.4230/LIPIcs.ESA.2017.16

Fast Dynamic Arrays

Authors: Philip Bille, Anders Roy Christiansen, Mikko Berggren Ettienne, and Inge Li Gørtz

Published in: LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017)

Abstract

We present a highly optimized implementation of tiered vectors, a data structure for maintaining a sequence of n elements supporting access in time O(1) and insertion and deletion in time O(n^e) for e > 0 while using o(n) extra space. We consider several different implementation optimizations in C++ and compare their performance to that of vector and set from the standard library on sequences with up to 10^8 elements. Our fastest implementation uses much less space than set while providing speedups of 40x for access operations compared to set and speedups of 10.000x compared to vector for insertion and deletion operations while being competitive with both data structures for all other operations.

Cite as

Philip Bille, Anders Roy Christiansen, Mikko Berggren Ettienne, and Inge Li Gørtz. Fast Dynamic Arrays. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 16:1-16:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{bille_et_al:LIPIcs.ESA.2017.16,
  author =	{Bille, Philip and Christiansen, Anders Roy and Ettienne, Mikko Berggren and G{\o}rtz, Inge Li},
  title =	{{Fast Dynamic Arrays}},
  booktitle =	{25th Annual European Symposium on Algorithms (ESA 2017)},
  pages =	{16:1--16:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-049-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{87},
  editor =	{Pruhs, Kirk and Sohler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.16},
  URN =		{urn:nbn:de:0030-drops-78309},
  doi =		{10.4230/LIPIcs.ESA.2017.16},
  annote =	{Keywords: Dynamic Arrays, Tiered Vectors}
}

Document

DOI: 10.4230/LIPIcs.FSTTCS.2016.36

Finger Search in Grammar-Compressed Strings

Authors: Philip Bille, Anders Roy Christiansen, Patrick Hagge Cording, and Inge Li Gortz

Published in: LIPIcs, Volume 65, 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)

Abstract

Grammar-based compression, where one replaces a long string by a small context-free grammar that generates the string, is a simple and powerful paradigm that captures many popular compression schemes. Given a grammar, the random access problem is to compactly represent the grammar while supporting random access, that is, given a position in the original uncompressed string report the character at that position. In this paper we study the random access problem with the finger search property, that is, the time for a random access query should depend on the distance between a specified index f, called the finger, and the query index i. We consider both a static variant, where we first place a finger and subsequently access indices near the finger efficiently, and a dynamic variant where also moving the finger such that the time depends on the distance moved is supported. Let n be the size the grammar, and let N be the size of the string. For the static variant we give a linear space representation that supports placing the finger in O(log(N)) time and subsequently accessing in O(log(D)) time, where D is the distance between the finger and the accessed index. For the dynamic variant we give a linear space representation that supports placing the finger in O(log(N)) time and accessing and moving the finger in O(log(D) + log(log(N))) time. Compared to the best linear space solution to random access, we improve a O(log(N)) query bound to O(log(D)) for the static variant and to O(log(D) + log(log(N))) for the dynamic variant, while maintaining linear space. As an application of our results we obtain an improved solution to the longest common extension problem in grammar compressed strings. To obtain our results, we introduce several new techniques of independent interest, including a novel van Emde Boas style decomposition of grammars.

Cite as

Philip Bille, Anders Roy Christiansen, Patrick Hagge Cording, and Inge Li Gortz. Finger Search in Grammar-Compressed Strings. In 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 65, pp. 36:1-36:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{bille_et_al:LIPIcs.FSTTCS.2016.36,
  author =	{Bille, Philip and Christiansen, Anders Roy and Cording, Patrick Hagge and Gortz, Inge Li},
  title =	{{Finger Search in Grammar-Compressed Strings}},
  booktitle =	{36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)},
  pages =	{36:1--36:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-027-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{65},
  editor =	{Lal, Akash and Akshay, S. and Saurabh, Saket and Sen, Sandeep},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2016.36},
  URN =		{urn:nbn:de:0030-drops-68717},
  doi =		{10.4230/LIPIcs.FSTTCS.2016.36},
  annote =	{Keywords: Compression, Grammars, Finger search, Algorithms}
}

Search Results

Documents authored by Christiansen, Anders Roy

Fast Dynamic Arrays

Abstract

Cite as

Finger Search in Grammar-Compressed Strings

Abstract

Cite as

Thanks for your feedback!

Could not send message