Paper by Erik D. Demaine

Reference:

Erik D. Demaine, Tim Kaler, Quanquan Liu, Aaron Sidford, and Adam Yedidia, “Polylogarithmic Fully Retroactive Priority Queues via Hierarchical Checkpointing”, in Proceedings of the 14th International Symposium on Algorithms and Data Structures (WADS 2015), Victoria, British Columbia, Canada, August 5–7, 2015, pages 263–275.

Abstract:

Since the introduction of retroactive data structures at SODA 2004 [1], a major open question has been the difference between partial retroactivity (where updates can be made in the past) and full retroactivity (where queries can also be made in the past). In particular, for priority queues, partial retroactivity is possible in O(log m) time per operation on a m-operation timeline, but the best previously known fully retroactive priority queue has cost Θ(√m log m) time per operation.

We address this open problem by providing a general logarithmic-overhead transformation from partial to full retroactivity called “hierarchical checkpointing,” provided that the given data structure is “time-fusible” (multiple structures with disjoint timespans can be fused into a timeline supporting queries of the present). As an application, we construct a fully retroactive priority queue which can insert an element, delete the minimum element, and find the minimum element, at any point in time, in O(log² m) amortized time per update and O(log² m log log m) time per query, using O(m log m) space. Our data structure also supports the operation of determining the time at which an element was deleted in O(log² m) time.

Availability:

The paper is available in PDF (335k).

See information on file formats.

[Google Scholar search]

Related papers:

RetroactiveSeparation_ISAAC2022 (Lower Bounds on Retroactive Data Structures)

RetroactiveSeparation_SWAT2018 (Nearly Optimal Separation Between Partially And Fully Retroactive Data Structures)

Retroactive_TALG (Retroactive Data Structures)