Paper by Erik D. Demaine
- Erik D. Demaine, John Iacono, and Stefan Langerman, “Retroactive Data Structures”, in Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2004), New Orleans, Louisiana, January 11–13, 2004, pages 274–283.
We introduce a new data structuring paradigm in which operations can be
performed on a data structure not only in the present but also in the past. In
this new paradigm, called retroactive data structures, the historical
sequence of operations performed on the data structure is not fixed. The data
structure allows arbitrary insertion and deletion of operations at arbitrary
times, subject only to consistency requirements. We initiate the study of
retroactive data structures by formally defining the model and its variants.
We prove that, unlike persistence, efficient retroactivity is not always
achievable, so we go on to present several specific retroactive data
- The paper is 10 pages.
- The paper is available in PostScript (208k), gzipped PostScript (63k), and PDF (138k).
- See information on file formats.
- [Google Scholar search]
- Related papers:
- Retroactive_TALG (Retroactive Data Structures)
- FullyRetroactive_WADS2015 (Polylogarithmic Fully Retroactive Priority Queues via Hierarchical Checkpointing)
- RetroactiveSeparation_SWAT2018 (Nearly Optimal Separation Between Partially And Fully Retroactive Data Structures)
- RetroactiveSeparation_ISAAC2022 (Lower Bounds on Retroactive Data Structures)
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated November 29, 2022 by