Banana Trees for the Persistence in Time Series Experimentally

By a time series we mean a linear list of real numbers, $c_0,c_2,\mathrm{\dots },c_{n-1}$, which we view as a piecewise linear map, $f:[0,n-1]\to ℝ$, with $f(i)=c_i$ for $0\le i\le n-1$. We refer to $i$ as an item and $c_i$ its value. A critical item is a local minimum or a local maximum of this map, and all other items are non-critical, e.g. item $i$ if . To simplify the discussion, we assume that the map is generic, by which we mean that its items have distinct values. In this case, the endpoints (items $0$ and $n-1$) are necessarily critical.

The sublevel set of $f$ at $t\in ℝ$, denoted $f_t=f^{-1}(-\mathrm{\infty },t]$, are the points $x\in [0,n-1]$ that satisfy $f(x)\le t$. When $t$ passes the value of a minimum from below, then the number of connected components of $f_t$ increases by $1$, and if $t$ passes the value of a maximum from below, the number of connected components decreases by $1$, unless the maximum is an endpoint, in which case the number does not change. Symmetrically, we call $f^t=f^{-1}[t,\mathrm{\infty })$ the superlevel set of $f$ at $t$. Observe that $f^t$ is the sublevel set of $-f$ at $-t$, and that the minima and maxima of $-f$ are the maxima and minima of $f$. Persistent homology tracks the evolution of the connected components while the sublevel set of $f$ grows, and formally defines when a component is born and when it dies. Complementing this with the same information for the superlevel sets of $f$, we get what is formally referred to as extended persistent homology; see [6] for details. It is best constructed in two phases:

• $\mathrm{■}$

  In Phase One, we track the connected components of the sublevel set, $f_t$, as $t$ increases from $-\mathrm{\infty }$ to $\mathrm{\infty }$. A component is born at the smallest value of $t$ at which a point of the component belongs to $f_t$, which is necessarily a minimum. The component dies when it merges with another component that was born earlier, which is necessarily at a maximum in the interior of $[0,n-1]$. The ordinary subdiagram of $f$ records the birth and death of every component with a point in the plane whose abscissa and ordinate are those values of $t$ at which the component is born and dies, respectively; see Figure 1.

• $\mathrm{■}$

  In Phase Two, we track the connected components of the superlevel set, $f^t$, as $t$ decreases from $\mathrm{\infty }$ to $-\mathrm{\infty }$. Birth and death are defined accordingly, and the components are recorded in the relative subdiagram.

By construction, the points in the ordinary subdiagram lie above and those of the relative subdiagram lie below the diagonal. The component born at the global minimum of $f$ is special because it does not die during Phase One. Instead, it dies at the global minimum of $-f$, which is the global maximum of $f$. In topological terms, this happens because the one connected component still alive at the beginning of Phase Two dies in relative homology when its first point enters the superlevel set. This class is represented by the sole point in the essential subdiagram. The extended persistence diagram is the disjoint union of the three subdiagrams. Hence, the diagram is a multi-set of points in ${ℝ}^2$, and so are the three subdiagrams, unless the map is generic, in which case the diagram is a set. See the left panel in Figure 1 for an example but note that it only shows a small number of points in the ordinary subdiagram. An important property of persistence diagrams is their stability with respect to small perturbation of the input data, which was first proved in [5].

The points in the persistence diagram can be characterized using the concept of a window introduced in [3]: start with a rectangular frame spanned by a minimum and a maximum in the graph of $f$ such that the minimum lies on the lower edge, and extend the frame horizontally as long as the graph does not intersect the upper edge in its interior. Call the initial frame the mid-panel, its extension the in-panel, and the symmetric extension for $-f$ the out-panel. As proved in [3], the min-max pair defines a point in the persistence diagram iff the graph of $f$ reaches the lower edge in the out-panel. In this case, we call the twice extended frame a triple-panel window. The corresponding double-panel window consists of the mid-panel and the in-panel but not the out-panel. Any two double-panel windows of $f$ are either disjoint or nested, a property not shared by the triple-panel windows. We use this property to augment the persistence diagram by drawing an arrow from a point to another, if the double-panel windows of the first point is nested inside the double-panel window of the other point, without any other window being nested between them. See Figure 1, which shows four double-panel windows and the corresponding points and arrows in the augmented persistence diagram. The displayed frames are indeed windows because each has an out-panel – next to the mid-panel and thus opposite to the in-panel – which extends as far as the horizontal projection of the minimum (a maximum of $-f$) to the graph of the function.

We sketch the banana trees while referring to [8] for the details. Suffice to say that they are based on the Cartesian tree introduced by Vuillemin [21], which stores a list of items in order such that each path from a leaf to the root is ordered by value. This tree has a unique decomposition into paths that correspond to double-panel windows, and the banana tree splits each path into two trails representing the windows nested inside the in-panel and the mid-panel of the corresponding window.

A time series represented by a piecewise linear function, $f$, is stored in two banana trees together with a linked list and two standard dictionaries. We call the first banana tree the up-tree of $f$ because it corresponds to Phase One of the persistence diagram construction. The second banana tree is the down-tree of $f$, which is the up-tree of $-f$. Because of this symmetry, it suffices to describe the up-tree of $f$. Its leaves are the minima of $f$, and its internal nodes are the maxima of $f$, with the exception of endpoint maxima, if they exist, since they are not critical in Phase One. Each point in the ordinary persistence diagram is a min-max pair, $(a,b)$, and it is represented by a banana that connects the leaf $a$ to the internal node $b$ with two parallel trails. The mid-trail is a doubly-linked list connecting $a$ to $b$ with the maxima that span windows nested in the mid-panel of the window of $a,b$, and the in-trail is symmetrically defined; see the right panel in Figure 1. The tree structure arises because the maxima belong to the similarly defined bananas of the nested windows. Each trail is sorted in the order of value but also in the order of location along the time series. For example, the mid-trail of the big banana in Figure 1 stores $a,s,q,b$, which monotonically increases in value and monotonically decreases in location. Compare this with the in-trail storing $a,v,b$, which monotonically increases in value and in location after we discard $b$. Indeed, we think of $b$ as part of the mid-trail while only connecting the in-trail to the rest of the tree without properly belonging to it. The global minimum of $f$ (not shown in Figure 1) is special because it is not paired in Phase One. Indeed, it is the extra leaf whose path upward does not end at an internal node. We therefore add a special root as the parent of the root, connected to the global minimum by the root banana. While there is only one root banana, there are possibly many leaf bananas, which are the bananas with two empty trails (beside the minimum and maximum they connect). Indeed, we call the number of nodes strictly between the minimum and maximum the length of the trail, which for trails of leaf bananas is necessarily zero. Another important concept is the nesting depth of a banana, which is the number of windows that contain the corresponding window. The root banana has nesting depth zero, and all other bananas have positive nesting depth.

Each update to a time series stored in a banana tree reduces to a sequence of elementary operations, which we name by their impact on the function, $f$. An interchange happens when two maxima or two minima swap the order of their values. Unless their locations are near each other, there is a good chance that an interchange does not have any effect on the banana tree. Otherwise, it is akin a rotation in a binary search tree, if the interchange is between two maxima, and akin a local rearrangement of the path decomposition, if the interchange is between two minima. A cancellation removes a min-max pair or, equivalently, the corresponding leaf banana, an anti-cancellation is the inverse of a cancellation, and a slide swaps the type of a critical item with that of a neighboring non-critical item. The latter three operations appear only a constant number of times whenever we adjust a value. Nevertheless, anti-cancellations present challenges to fast implementation as we have to find out where the new banana is to be inserted, and this search is not supported by any special purpose data structure. On the other hand, multiple interchanges may happen in sequence, so it is important to charge the time for processing each to a change in the persistence diagram. We refer to [8] for details.

We write $\gamma \sim 𝒩(\mu ,\sigma )$ for a normally distributed random variable with mean $\mu$ and standard deviation $\sigma$. Given $\mu ,\sigma$, a random walk of length $n$ is a function, $r=r_{\mu ,\sigma }$, from the first $n$ non-negative integers to the reals, defined by

in which the ${\gamma }_i\sim 𝒩(\mu ,\sigma )$ are independent. The random walk is unbiased if $\mu =0$ and biased if $\mu \ne 0$. We assume $\sigma =1$ unless stated otherwise.

To evaluate the performance of local updates, we change the value of a single item, and since it depends on the amount, we fix parameters $\mathrm{\Delta }\in ℝ$ and $k\in \mathbb{N}$ and do $2k+1$ parallel updates by changing the value of the $i$-th item from $r(i)$ to $r(i)+{\delta }_j$, with ${\delta }_j=\frac{j}{k}\mathrm{\Delta }$ for all integers $j$ with $-k\le j\le k$. For the experiments, we pick $\mathrm{\Delta }=5.0$ or $50.0$ and $k=10$, while doing the update on a random walk of length between ${10}^2$ and ${10}^6$ generated for $\mu \in [-1,1]$ and $\sigma =1$. Each experiment is repeated one hundred times and averages as well as deviations from the average are reported. For each experiment, we also measure the time to run Gudhi on the walk after the value change. This provides the appropriate reference time, since Gudhi needs to recompute the persistence diagram from scratch after each update.

To evaluate the performance of topological updates, we pick a fraction, $c\in (0,1)$, generate a random walk of length $n$, and then cut it into a left walk containing the first $\lfloor cn\rfloor$ items and a right walk containing the remaining $\lceil (1-c)n\rceil$ items. There are two such updates, which we now define. To split, we first construct the banana tree of the entire random walk, which we then cut into two banana trees, one for the left and the other for the right walk. To glue, we first construct the banana trees of the left and right walks, which we then combine to a single banana tree for the walk of length $n$. Doing this for fractions $c\in \{0.1,0.3,0.5,0.7,0.9\}$, we compare the time to split with the time used by Gudhi to construct the persistence diagrams of the left and right walks, and the time to glue with the time used by Gudhi to construct the persistence diagram of the entire random walk.

We focus on three structural properties of banana trees, which have direct implications for the running time of our algorithms: the number of critical items, the nesting depth of bananas, and the lengths of trails. Since a banana tree does not store non-critical items, its number of nodes is the number of critical items. In an unbiased random walk, the expected number of critical items is $50\%$ of all items. This fraction decreases when the bias increases, with about $27\%$ for $\mu =\pm 1$; see the left panel in Figure 2 for more detailed information.

The middle panel of Figure 2 shows the average nesting depth of a leaf banana for an unbiased random walk, which appears to scale like the logarithm of the number of items. In the unbiased case, even the maximum nesting depth seems to be small (about $13$ on average for a random walk of length $2\cdot {10}^6$), and scale logarithmically in the number of items. With increasing bias, the maximum nesting depth decreases, to about $4$ at $\mu =\pm 1$; see the right panel of Figure 2. This is because in the biased case, there are fewer critical items but also the bananas tend to arrange in parallel rather than inside each other. We observe that the nesting depth is about the same on average in up-trees and down-trees, both for biased and unbiased random walks, so our results hold for both trees.

For topological reasons, the mid-trails of the up-tree are the mid-trails of the down-tree, except that they are upside down. In contrast, the in-trails of the two trees are not directly related because the in-panels in one direction become the out-panels in the other. Notwithstanding, we observe that the length of the in-trails in the up-tree and the mid-trails in the down tree are very similar on the average, and by symmetry the same holds for the mid-trails in the up-tree and the in-trails in the down-tree. These two facts do not contradict each other, because for biased data most of the critical items belong to the root banana, which does not adhere to the topological constraints just mentioned. Let us therefore focus on the up-tree. The left panel in Figure 3 shows how the average length of in- and mid-trails depends on the bias. In the unbiased case, both types of trails have the same length on average. For positive $\mu$, the mid-trails tend to be longer than the in-trails, while the reverse happens for negative $\mu$. The main cause for this trend is the longest trail, which starts to dominate the others in length as the bias increases; see the right panel in Figure 3. Assuming $\mu >0$, the global minimum and maximum tend to lie to the left and right of the middle, respectively, with the majority of the items between them. By convention, the connecting in-trail and mid-trail contain the items to the left and right of the global minimum, respectively. This explains why the mid-trail dominates in this case, and why the in-trail dominates when . Indeed, for $\mu =\pm 1$, we observe about $95\%$ of the internal nodes (the local maxima) on the longest trail.

We evaluate the performance of banana trees when the value of a single item changes by $\delta$. Note that the corresponding update is a combination of some number of interchanges and at most one cancellation, at most one anti-cancellation, and at most two slides [8]. Not surprisingly, the time increases with the amount of change. For example, there is no effect at all on the persistence diagram for about $70\%$ of the updates with $\delta =\pm 0.26$, for about $36\%$ of the updates with $\delta =\pm 0.79$, but only about $1\%$ for updates with $\delta =\pm 3.4$. Taking this into account, it is not surprising that banana trees are faster than Gudhi when $\delta =\pm 0.26$ for all lengths of random walks we tried.

The left panel in Figure 4 focuses on the case $\delta =\pm 5.0$. As indicated by the vertical dashed and dotted lines, banana trees are faster than Gudhi for all random walks of length $n\ge 1059$, and faster in the median for all $n\ge 144$. Not shown in the panel is that the speedup decreases with increasing bias. In particular, for $n={10}^6$, the speedup of $612$ at $\mu =0$ decreases to $258$ at $\mu =1$, and for $n=1059$, the speedup of $6.0$ at $\mu =0$ decreases to $2.9$ at $\mu =1$. This can be explained by recalling that for large bias the majority of the internal nodes belong to the longest trail, which connects the global minimum to the global maximum. Hence, items with similar values are likely to be near each other and thus require interchanges when an update is performed. However, even for a large change, such as for $\delta =\pm 50.0$, maintaining the banana tree is still faster than reconstructing the persistence diagram with Gudhi. For example, the median speedup for $n={10}^4$ exceeds $10$ and for $n={10}^6$ it exceeds $100$.

We call the operations of cutting a list into two, and concatenating two lists to one topological because they change the number of lists in the overall organization of the data. We begin with evaluating the performance of cutting a random walk. The middle panel in Figure 4 shows the speedup over Gudhi when we cut a biased or unbiased random walk in half. In the unbiased case, the speedup increases with the length of the walk. Recalling the discussion of structural properties, this can be rationalized by noticing that the maximum nesting depth bounds the number of bananas that need to be split, and the trail length bounds the time to reorganize bananas. The maximum nesting depth scales like $\log n$ and the average trail length is only $0.5$, so we anticipate logarithmic time for splitting, which we indeed observe in our experiments. Altering the position of the cut increases the speedup, namely by about $2\%$ for $c=0.5\pm 0.2$ and by about $7\%$ for $c=0.5\pm 0.4$.

The advantage of the banana tree over Gudhi diminishes when the random walks get progressively more biased. The reason is again that the larger the bias, the larger the fraction of internal nodes in the longest trail of the banana tree. Splitting the corresponding banana requires the resetting of many pointers stored in nodes along this trail, which in some cases costs time proportional to the number of critical items, which we indeed observe in our experiments. Unfortunately, this more than compensates for the low nesting depth, which guarantees that only a small number of bananas need to be split. The upper half of Table 1 shows the running time and the speedup over Gudhi for cutting a random walk in half.

We finally address the reverse operation, that of concatenating two random walks or, correspondingly, of gluing two banana trees. The curves in the right panel of Figure 4 are similar to those in the middle panel, which suggests that the performance is similar to that of cutting, which is confirmed by the numbers in Table 1. For $n\le {10}^4$, gluing appears to be slightly faster than splitting, but the difference is less clear already for $n={10}^6$.

The size of the augmented persistence diagram (number of points and arrows) is proportional to the number of critical items. There are configurations in which a single update changes almost the entire diagram and thus takes time at least linear in the number of such items. We construct such worst-case inputs and study the performance of banana trees when confronted with such data.

Consider first the operation that increases the value of the marked item in the left panel of Figure 5. Initially, we have a linear sequence of double-panel windows, each nested inside the next. When the value of the marked item passes that of its left neighbor, an anti-cancellation adds the banana they span to the banana tree, and its window is nested inside the others. As we increase the value further, the marked item interchanges with the maxima to its right, each time moving up one level within the sequence of windows. When the marked item finally becomes the global maximum, it will have interchanged with all other maxima, which takes $\mathrm{\Theta }(n)$ time. For $n={10}^2$ and $n={10}^6$, we measured $3.4\mu \mathrm{s}$ and $4.7\mathrm{ms}$ on average, respectively. This corresponds to a median speedup by a factor of $0.05$ and $0.02$ if compared with Gudhi, which is really a slowdown by a factor of $20$ and $50$, respectively.

Consider second the operation that cuts the time series in the right panel of Figure 5 in the middle, which is marked by the vertical dashed line. We observe an average running time between $10\mu \mathrm{s}$ at $n={10}^2$ and $72\mathrm{m}\mathrm{s}$ at $n={10}^6$. Compare this with an average running time of $7\mu \mathrm{s}$ at $n={10}^2$ and $48\mathrm{m}\mathrm{s}$ at $n={10}^6$ for concatenating the two lists back to the original length. This comparison agrees with the earlier observation that gluing banana trees is slightly faster than splitting them. Table 2 lists the speedup if compared to Gudhi, which for a factor less than $1$ is really a slowdown. To create a more informative experiment, we interpolate between these time series and unbiased walks, with drastic improvements even for small $\lambda >0$; see Table 2. Indeed, the noise quickly flattens the banana tree by decreasing the length of trails, which explains the improvement.

Random walks are not periodic, but real-world time series often exhibit some amount of periodicity, at least approximately. To study banana trees under these conditions, we construct what we call quasi-periodic inputs. This term does not have a mathematical definition, and for our experiments just means a periodic signal that is randomly perturbed. Specifically, we generate such input by modifying the iterative construction in (1):

in which the ${\eta }_i\sim 𝒩({\mu }_i,\sigma )$ are independent and normally distributed, with the mean changing periodically, ${\eta }_i=\sin (2\pi \omega i)$, as governed by the frequency parameter , which we fix to $\omega =5/n$. It will be useful to compare the influence of the standard deviation, so we no longer assume $\sigma =1$.

For large $\sigma$, the banana trees of the time series show the features we have seen for unbiased random walks, while for small $\sigma$, they locally behave like biased random walks. For example, for $\sigma =1$, we observe about $37\%$ of the items to be critical, while for $\sigma =0.5$ and $\sigma =0.02$ only about $21\%$ and $1\%$ of the items are critical, on average. Like the number of critical items, also the maximum nesting depth for quasi-periodic signals is similar to that of random walks: it scales like $\log n$ for large $\sigma$ and decreases as $\sigma$ goes to $0$. In contrast, the average nesting depth is independent of $n$, ranging from $2$ to $4.7$ with mean $2.4$. The behavior of the trail length is illustrated in Figure 6. As shown in the left panel, the average trail length is about $0.5$, with consistently shorter in-trails than mid-trails, on average. This difference is more pronounced for small $\sigma$, when the quasi-periodic signal behaves more like a biased rather than unbiased random walk. The middle and right panels show how the fraction of internal nodes on the longest trail increases as $\sigma$ goes to $0$.

We conclude that banana trees on quasi-periodic signals with large standard deviation resemble unbiased random walks in terms of their structural parameters, and drift toward biased random walks as the standard deviation goes to $0$.

We analyze structural properties of banana trees constructed on three types of real-world time series:

• $\mathrm{■}$

  electrocardiography (ECG) data from PhysioNet [13, 1, 20]; limiting ourselves to recordings of length at least ${10}^5$, each separated into up to 12 leads, gives 32443 time series in total;

• $\mathrm{■}$

  audio data from EasyCom [9], of which we use 1336 audio files;

• $\mathrm{■}$

  physical activity data from PAMAP2 [19] (temperature, heart rate along with recordings from accelerometers, gyroscopes, and magnetometers), of which we use 560 time series.

We preprocess the data by adding uniformly distributed noise to ensure all values are distinct, making sure the noise is small enough so it breaks ties but does not otherwise alter the ordering.

We observe that the average max nesting depth for the three data sets is only a small factor larger than for unbiased random walks; see the middle three columns in Table 3. The largest maximum nesting depth for PhysioNet data is a bit higher, by a factor $6.3$, but $99\%$ of the time series from this data have maximum nesting depth at most $1.68$ times that for unbiased random walks. The average trail lengths are again similar to those of unbiased random walks – see the last two columns, with standard deviation about $0.05$ throughout – and so are the fractions of items in the longest trails, whose geometric means are $0.8\%,0.008\%,0.1\%$ of all critical items for the in-trails and $0.8\%,0.008\%,0.2\%$ of all critical items for the mid-trails in the three data sets, compared with about $0.3\%$ and $0.4\%$ in unbiased random walks.