ICS Theory Group

ICS 269, Spring 2004: Theory Seminar

28 May 2004:
Retroactive Data Structures
Michael Nelson

This is a presentation of the paper "Retroactive Data Structures" by Erik D. Demaine, John Iacono, and Stefan Langerman, SODA 2004.

The authors introduce a new data structuring paradigm called retroactive data structures.  In these data structures, the historical sequence of operations performed on the data structure is not fixed.  They allow the insertion and deletion of operations at arbitrary past times, subject only to consistency.  The authors initiate the study of retroactive data structures by formally defining the model and its variants.  They show that retroactivity differs from persistence in that efficient retroactivity is not always achievable, and therefore go on to present several specific retroactive data structures as well as techniques for transforming certain classes of data structures into their retroactive equivalents.  I will present the retroactive model and touch on a selection of their results.