LIPIcs.SEA.2018.19.pdf
- Filesize: 482 kB
- 13 pages
Document
Experimental Study of Compressed Stack Algorithms in Limited Memory Environments
Authors
-
Part of:
Volume:
17th International Symposium on Experimental Algorithms (SEA 2018)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Symposium on Experimental Algorithms (SEA) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2018-06-19
Cite AsGet BibTex
Jean-François Baffier, Yago Diez, and Matias Korman. Experimental Study of Compressed Stack Algorithms in Limited Memory Environments. In 17th International Symposium on Experimental Algorithms (SEA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 103, pp. 19:1-19:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.SEA.2018.19
https://doi.org/10.4230/LIPIcs.SEA.2018.19
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.
Subject Classification
ACM Subject Classification
- Theory of computation → Computational geometry
Keywords
- Stack algorithms
- time-space trade-off
- convex hull
- implementation
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Greg Aloupis. A history of linear-time convex hull algorithms for simple polygons, 2005. URL: http://cgm.cs.mcgill.ca/~athens/cs601/.
-
Boris Aronov, Matias Korman, Simon Pratt, André van Renssen, and Marcel Roeloffzen. Time-space trade-offs for triangulating a simple polygon. Journal of Computational Geometry, 8(1):105-124, 2017.
- Tetsuo Asano, Kevin Buchin, Maike Buchin, Matias Korman, Wolfgang Mulzer, Günter Rote, and André Schulz. Memory-constrained algorithms for simple polygons. Computational Geometry: Theory and Applications, 46(8):959-969, 2012. Special issue of selected papers from the 28th European Workshop on Computational Geometry. URL: http://dx.doi.org/10.1016/j.comgeo.2013.04.005.
-
Tetsuo Asano, Kevin Buchin, Maike Buchin, Matias Korman, Wolfgang Mulzer, Günter Rote, and André Schulz. Memory-constrained algorithms for simple polygons. Computational Geometry: Theory and Applications, 46(8):959-969, 2013.
-
Tetsuo Asano, Wolfgang Mulzer, Günter Rote, and Yajun Wang. Constant-work-space algorithms for geometric problems. Journal of Computational Geometry, 2(1):46-68, 2011.
- Jean-François Baffier, Yago Diez, and Matias Korman. Compressed stack library (C++). https://github.com/Azzaare/CompressedStacks.cpp.git, 2016.
- Jean-François Baffier, Yago Diez, and Matias Korman. Compressed stack library (Julia). https://github.com/Azzaare/CompressedStacks.jl.git, 2016.
- Jean-François Baffier, Yago Diez, and Matias Korman. Experimental study of compressed stack algorithms in limited memory environments. CoRR, abs/1706.04708, 2017. URL: http://arxiv.org/abs/1706.04708.
-
Niranka Banerjee, Sankardeep Chakraborty, Venkatesh Raman, Sasanka Roy, and Saket Saurabh. Time-space tradeoffs for dynamic programming algorithms in trees and bounded treewidth graphs. In COCOON, pages 349-360, 2015.
- Luis Barba, Matias Korman, Stefan Langerman, Kunihiko Sadakane, and Rodrigo I. Silveira. Space-time trade-offs for stack-based algorithms. Algorithmica, 72(4):1097-1129, 2014. URL: http://dx.doi.org/10.1007/s00453-014-9893-5.
-
Luis Barba, Matias. Korman, Stefan Langerman, and Rodrigo. I. Silveira. Computing the visibility polygon using few variables. Computational Geometry: Theory and Applications, 47(9):918-926, 2013.
-
Jonas Cleve and Wolfgang Mulzer. An experimental study of algorithms for geodesic shortest paths in the constant workspace model. In EuroCG, pages 165-168, 2017.
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, 3rd Edition. MIT Press, 2009. URL: http://mitpress.mit.edu/books/introduction-algorithms.
-
Mark de Berg, Mark van Kreveld, Mark Overmars, and Otfried Schwarzkopf. Computational Geometry: Algorithms and Applications. Springer-Verlag, 3rd edition, 2008.
-
Matias Korman. Memory-constrained algorithms. In Encyclopedia of Algorithms, pages 1260-1264. Springer, 2016.
-
Matias Korman, Wolfgang Mulzer, André van Renssen, Marcel Roeloffzen, Paul Seiferth, and Yannik Stein. Time-space trade-offs for triangulations and Voronoi diagrams. In Algorithms and Data Structures Symposium (WADS), pages 482-494, 2015.
-
Matias Korman, Wolfgang Mulzer, André van Renssen, Marcel Roeloffzen, Paul Seiferth, and Yannik Stein. Time-space trade-offs for triangulations and voronoi diagrams. Computational Geometry: Theory and Applications, 2017. Special issue of selected papers from the 31st European Workshop on Computational Geometry. In press.
- Der-Tsai Lee. On finding the convex hull of a simple polygon. International Journal of Parallel Programming, 12(2):87-98, 1983. URL: http://dx.doi.org/10.1007/BF00993195.
- Nicholas Nethercote, Robert Walsh, and Jeremy Fitzhardinge. Building workload characterization tools with valgrind. In IISWC, pages 2-2, Oct 2006. URL: http://dx.doi.org/10.1109/IISWC.2006.302723.