Seminar | Study of compressed stack algorithms in limited memory environment

A seminar of the A3SI and LRT teams of the LIGM (joint research unit of Paris Est University) took place on Friday, June 22 from 1:30 pm to 2:30 pm at ESIEE Paris.

Study of compressed stack algorithms in limited memory environment
Jean-Francois Baffier
Tokyo Intistute of Technology

Abstract: The need to run algorithms on limited-memory devices motivated our consideration for data structure in the settings where there is only a limited amount of memory available (apart from the input representation). We proposed a practical implementation of the theoretical work of Barba et al.. In their work, they introduce a class of algorithms called stack algorithms: algorithms that scan the input in a streaming fashion and have a stack as their space bottleneck. For those algorithms, Barba et al. introduce a new data structure, called compressed stack, that gives a general time-space trade-off: they can reduce the amount of memory used by the algorithm at the cost of increasing running time. Specifically, stack algorithms can run in O(n^(1+1/log_p(n) ) ) time using O(p.log_p(n) ) space for any parameter p ∈ {2,...,n} (instead of Θ(n) time and space when a normal stack is used).

All of our algorithms are available in C ++ (and Julia) under MIT licenses at https://github.com/Azzaare/CompressedStacks.cpp.git

The article presenting this work is available on arxiv: https://arxiv.org/abs/1706.04708

Jean-Francois Baffier graduated Master course at University Paris XI in 2011 and got Ph.D. from the University of Tokyo in 2015. He was a member of the ERATO Kawarabayashi Large Project from May 2015 to August 2017 in Tokyo and Sendai.

His main research topic covers modeling of failures and routing in Networks. Other research topics involve Game analysis and AI for Games (in particular Starcraft), but also Local Search algorithm (HPC) and limited memory algorithms.

He is currently supported by the Japanese Society for the Promotion of Science as a JSPS-CNRS research fellow (Sept. 2017-2019) and hosted at the Tokyo Intistute of Technology (Japan).