Paper by Erik D. Demaine

Reference:

Erik D. Demaine, John Iacono, and Stefan Langerman, “Retroactive Data Structures”, ACM Transactions on Algorithms, volume 3, number 2, May 2007, Article 13.

Abstract:

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. Thus, we present efficient retroactive data structures for queues, doubly ended queues, priority queues, union-find, and decomposable search structures.

Length:

The paper is 21 pages.

Availability:

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)