Dynamically Maintaining the Persistent Homology of Time Series

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.

arXiv commentCorrected the statement and proof of Theorem 5.2; added a missing edge-case to the anti-cancellation algorithm