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

Baffier, Jean-François ; Diez, Yago ; Korman, Matias

Experimental Study of Compressed Stack Algorithms in Limited Memory Environments

pdf-format:
LIPIcs-SEA-2018-19.pdf (0.5 MB)

Abstract

The compressed stack is a data structure designed by Barba et al. (Algorithmica 2015) that allows to reduce the amount of memory needed by a certain class of algorithms at the cost of increasing its runtime. In this paper we introduce the first implementation of this data structure and make its source code publicly available.
Together with the implementation we analyse the performance of the compressed stack. In our synthetic experiments, considering different test scenarios and using data sizes ranging up to 2^{30} elements, we compare it with the classic (uncompressed) stack, both in terms of runtime and memory used.
Our experiments show that the compressed stack needs significantly less memory than the usual stack (this difference is significant for inputs containing 2000 or more elements). Overall, with a proper choice of parameters, we can save a significant amount of space (from two to four orders of magnitude) with a small increase in the runtime (2.32 times slower on average than the classic stack). These results hold even in test scenarios specifically designed to be challenging for the compressed stack.

BibTeX - Entry

@InProceedings{baffier_et_al:LIPIcs:2018:8954,
  author =	{Jean-Fran{\c{c}}ois Baffier and Yago Diez and Matias Korman},
  title =	{{Experimental Study of Compressed Stack Algorithms in Limited Memory Environments}},
  booktitle =	{17th International Symposium on Experimental Algorithms  (SEA 2018)},
  pages =	{19:1--19:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-070-5},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{103},
  editor =	{Gianlorenzo D'Angelo},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/8954},
  URN =		{urn:nbn:de:0030-drops-89549},
  doi =		{10.4230/LIPIcs.SEA.2018.19},
  annote =	{Keywords: Stack algorithms, time-space trade-off, convex hull, implementation}
}

Keywords: Stack algorithms, time-space trade-off, convex hull, implementation
Collection: 17th International Symposium on Experimental Algorithms (SEA 2018)
Issue Date: 2018
Date of publication: 19.06.2018
Supplementary Material: https://github.com/Azzaare/CompressedStacks.cpp

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