Retroactive Data Structures

Erik D. Demaine; John Iacono; Stefan Langerman

Retroactive Data Structures

Erik D. Demaine, John Iacono, Stefan Langerman

Research output: Contribution to conference › Paper › peer-review

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 language	English (US)
Pages	274-283
Number of pages	10
State	Published - 2004
Event	Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms - New Orleans, LA., United States Duration: Jan 11 2004 → Jan 13 2004

Other

Other	Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms
Country/Territory	United States
City	New Orleans, LA.
Period	1/11/04 → 1/13/04

ASJC Scopus subject areas

Software
General Mathematics

Cite this

@conference{afc56078e5ac41f5ba64f2869d7ba50c,

title = "Retroactive Data Structures",

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.",

author = "Demaine, {Erik D.} and John Iacono and Stefan Langerman",

year = "2004",

language = "English (US)",

pages = "274--283",

note = "Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms ; Conference date: 11-01-2004 Through 13-01-2004",

}

TY - CONF

T1 - Retroactive Data Structures

AU - Demaine, Erik D.

AU - Iacono, John

AU - Langerman, Stefan

PY - 2004

Y1 - 2004

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=1842435923&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=1842435923&partnerID=8YFLogxK

M3 - Paper

AN - SCOPUS:1842435923

SP - 274

EP - 283

T2 - Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms

Y2 - 11 January 2004 through 13 January 2004

ER -

Retroactive Data Structures

Abstract

Other

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this