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 \(\varTheta (\sqrt{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 ^2 m)\) amortized time per update and \(O(\log ^2 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 ^2 m)\) time.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Demaine, E.D., Iacono, J., Langerman, S.: Retroactive data structures. ACM Transactions on Algorithms 3, 13 (2007). Originally in SODA 2003
Giora, Y., Kaplan, H.: Optimal dynamic vertical ray shooting in rectilinear planar subdivisions. ACM Transactions on Algorithms (TALG) 5, 28 (2009)
Bentley, J.L.: Solutions to klees rectangle problems. Technical report, Carnegie Mellon University (1977)
Galperin, I., Rivest, R.L.: Scapegoat trees. In: Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete algorithms, pp. 165–174. Society for Industrial and Applied Mathematics (1993)
Sleator, D.D., Tarjan, R.E.: Self-adjusting binary search trees. Journal of the ACM (JACM) 32, 652–686 (1985)
Bender, M.A., Demaine, E.D., Farach-Colton, M.: Cache-oblivious b-trees. In: Proceedings of the 41st Annual Symposium on Foundations of Computer Science, pp. 399–409. IEEE (2000)
Arge, L., Vitter, J.S.: Optimal dynamic interval management in external memory. In: Proceedings of the 37th Annual Symposium on Foundations of Computer Science, pp. 560–569. IEEE (1996)
Frederickson, G.N., Johnson, D.B.: The complexity of selection and ranking in \(X+Y\) and matrices with sorted columns. Journal of Computer and System Sciences 24, 197–208 (1982)
Rauh, A., Arce, G.: A fast weighted median algorithm based on quickselect. In: 2010 17th IEEE International Conference on Image Processing (ICIP), pp. 105–108 (2010)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Demaine, E.D., Kaler, T., Liu, Q., Sidford, A., Yedidia, A. (2015). Polylogarithmic Fully Retroactive Priority Queues via Hierarchical Checkpointing. In: Dehne, F., Sack, JR., Stege, U. (eds) Algorithms and Data Structures. WADS 2015. Lecture Notes in Computer Science(), vol 9214. Springer, Cham. https://doi.org/10.1007/978-3-319-21840-3_22
Download citation
DOI: https://doi.org/10.1007/978-3-319-21840-3_22
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-21839-7
Online ISBN: 978-3-319-21840-3
eBook Packages: Computer ScienceComputer Science (R0)