Retroactive Data Structures

Erik D. Demaine, John Iacono, Stefan Langerman

    Research output: Contribution to conferencePaper

    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, so we go on to present several specific retroactive data structures.

    Original languageEnglish (US)
    Pages274-283
    Number of pages10
    StatePublished - 2004
    EventProceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms - New Orleans, LA., United States
    Duration: Jan 11 2004Jan 13 2004

    Other

    OtherProceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms
    CountryUnited States
    CityNew Orleans, LA.
    Period1/11/041/13/04

    ASJC Scopus subject areas

    • Software
    • Mathematics(all)

    Fingerprint Dive into the research topics of 'Retroactive Data Structures'. Together they form a unique fingerprint.

  • Cite this

    Demaine, E. D., Iacono, J., & Langerman, S. (2004). Retroactive Data Structures. 274-283. Paper presented at Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, New Orleans, LA., United States.