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.MFCS.2018.65
URN: urn:nbn:de:0030-drops-96478
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9647/
Go to the corresponding LIPIcs Volume Portal

Kammer, Frank ; Sajenko, Andrej

Extra Space during Initialization of Succinct Data Structures and Dynamical Initializable Arrays

pdf-format:
LIPIcs-MFCS-2018-65.pdf (0.5 MB)

Abstract

Many succinct data structures on the word RAM require precomputed tables to start operating. Usually, the tables can be constructed in sublinear time. In this time, most of a data structure is not initialized, i.e., there is plenty of unused space allocated for the data structure. We present a general framework to store temporarily extra buffers between the user defined data so that the data can be processed immediately, stored first in the buffers, and then moved into the data structure after finishing the tables. As an application, we apply our framework to Dodis, Patrascu, and Thorup's data structure (STOC 2010) that emulates c-ary memory and to Farzan and Munro's succinct encoding of arbitrary graphs (TCS 2013). We also use our framework to present an in-place dynamical initializable array.

BibTeX - Entry

@InProceedings{kammer_et_al:LIPIcs:2018:9647,
  author =	{Frank Kammer and Andrej Sajenko},
  title =	{{Extra Space during Initialization of Succinct Data Structures and Dynamical Initializable Arrays}},
  booktitle =	{43rd International Symposium on Mathematical Foundations  of Computer Science (MFCS 2018)},
  pages =	{65:1--65:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-086-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{117},
  editor =	{Igor Potapov and Paul Spirakis and James Worrell},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9647},
  URN =		{urn:nbn:de:0030-drops-96478},
  doi =		{10.4230/LIPIcs.MFCS.2018.65},
  annote =	{Keywords: space efficiency, succinct c-ary memory, dynamic graph representation}
}

Keywords: space efficiency, succinct c-ary memory, dynamic graph representation
Collection: 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)
Issue Date: 2018
Date of publication: 27.08.2018

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