Paper by Erik D. Demaine
- Erik D. Demaine, John Iacono, and Stefan Langerman, “Retroactive Data Structures”, ACM Transactions on Algorithms, volume 3, number 2, May 2007, Article 13.
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
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.
Thus, we present efficient retroactive data structures for queues,
doubly ended queues, priority queues, union-find, and decomposable
- The paper is 21 pages.
- The paper is available in PostScript (483k), gzipped PostScript (200k), and PDF (255k).
- See information on file formats.
- [Google Scholar search]
- Related papers:
- Retroactive_SODA2004 (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 December 15, 2022 by