Dynamically maintaining the persistent homology of time series
Cultrera di Montesano S, Edelsbrunner H, Henzinger MH, Ost L. 2024. Dynamically maintaining the persistent homology of time series. Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SODA: Symposium on Discrete Algorigthms, 243–295.
Download (ext.)
Conference Paper
| Published
| English
Author
Editor
Woodruff, David P.
Department
Grant
Abstract
We present a dynamic data structure for maintaining the persistent homology of a time series of real numbers. The data structure supports local operations, including the insertion and deletion of an item and the cutting and concatenating of lists, each in time O(log n + k), in which n counts the critical items and k the changes in the augmented persistence diagram. To achieve this, we design a tailor-made tree structure with an unconventional representation, referred to as banana tree, which may be useful in its own right.
Publishing Year
Date Published
2024-01-04
Proceedings Title
Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)
Acknowledgement
The first and second authors are funded by the European Research Council under the European Union’s Horizon 2020 research and innovation programme, ERC grant no. 788183,“Alpha Shape Theory Extended (Alpha)”, by the Wittgenstein Prize, FWF grant no. Z 342-N31, and by the DFG Collaborative Research Center TRR 109, FWF grant no. I 02979-N35.The third author received funding by the European Research Council under the European Union’s Horizon 2020research and innovation programme, ERC grant no. 101019564, “The Design of Modern Fully Dynamic DataStructures (MoDynStruct)”, and by the Austrian Science Fund through the Wittgenstein Prize with FWF grant no. Z 422-N, and also by FWF grant no. I 5982-N, and by FWF grant no. P 33775-N, with additional funding from the netidee SCIENCE Stiftung, 2020–2024. The fourth author is funded by the Vienna Graduate School on Computational Optimization, FWF project no. W1260-N35.
Page
243 - 295
Conference
SODA: Symposium on Discrete Algorigthms
Conference Location
Alexandria, VA, USA
Conference Date
2024-01-07 – 2024-01-10
IST-REx-ID
Cite this
Cultrera di Montesano S, Edelsbrunner H, Henzinger MH, Ost L. Dynamically maintaining the persistent homology of time series. In: Woodruff DP, ed. Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). Society for Industrial and Applied Mathematics; 2024:243-295. doi:10.1137/1.9781611977912.11
Cultrera di Montesano, S., Edelsbrunner, H., Henzinger, M. H., & Ost, L. (2024). Dynamically maintaining the persistent homology of time series. In D. P. Woodruff (Ed.), Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) (pp. 243–295). Alexandria, VA, USA: Society for Industrial and Applied Mathematics. https://doi.org/10.1137/1.9781611977912.11
Cultrera di Montesano, Sebastiano, Herbert Edelsbrunner, Monika H Henzinger, and Lara Ost. “Dynamically Maintaining the Persistent Homology of Time Series.” In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), edited by David P. Woodruff, 243–95. Society for Industrial and Applied Mathematics, 2024. https://doi.org/10.1137/1.9781611977912.11.
S. Cultrera di Montesano, H. Edelsbrunner, M. H. Henzinger, and L. Ost, “Dynamically maintaining the persistent homology of time series,” in Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Alexandria, VA, USA, 2024, pp. 243–295.
Cultrera di Montesano S, Edelsbrunner H, Henzinger MH, Ost L. 2024. Dynamically maintaining the persistent homology of time series. Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SODA: Symposium on Discrete Algorigthms, 243–295.
Cultrera di Montesano, Sebastiano, et al. “Dynamically Maintaining the Persistent Homology of Time Series.” Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), edited by David P. Woodruff, Society for Industrial and Applied Mathematics, 2024, pp. 243–95, doi:10.1137/1.9781611977912.11.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]
Link(s) to Main File(s)
Access Level
Open Access
Material in ISTA:
Dissertation containing ISTA record
Export
Marked PublicationsOpen Data ISTA Research Explorer
Sources
arXiv 2311.01115
Google Scholar