# Proof of metric properties for the Selective Temporal Hamming distance

Sylvain Marié

<figure><img src="image_1.png" /></figure>

## To cite this version:

Sylvain Marié. Proof of metric properties for the Selective Temporal Hamming distance. 2025. hal-05328460

HAL Id: hal-05328460

https://hal.science/hal-05328460v1

Submitted on 23 Oct 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Proof of metric properties for the Selective Temporal Hamming distance

Sylvain Marié[0000-0002-5929-1047]

Schneider Electric Industries, 160, avenue des Martyrs, 38000 Grenoble, France
sylvain.marie@se.com

**Abstract.** The original article introducing the Selective Temporal Hamming similarity and distance states that it complies with proper metric properties (*positivity*, *symmetry*, *distinguishability* and *triangular inequality*). This paper provides a proof.

**Keywords:** STH · distance · metric · similarity · kernel · Hamming · Jaccard · aperiodic · non-uniform · categorical · timeseries · CTS · temporal · duration · sequence · discrete event systems · DES · finite state · event · alarm · transition · multi-state

# 1 Selective Temporal Hamming

## 1.1 Definitions

We consider two categorical timeseries $s_i$ and $s_j$ with categorical states in $S$ and timestamps in $\Omega$. We consider the collection $\mathcal{I}_{ij} = \{\iota_k\}$ of time intervals defined by the union of all timestamps in $s_i$, $s_j$ and note

* $\Delta_i$ the duration of an interval $i$

* $\sigma_i^t$ the value of series $s_i$ on interval $i$

We remind the definition of the Selective Temporal Hamming similarity [3] for any partition of $S$ into states of interest $S_I$, other states $S_O$, and excluded states $S_E$; $S = S_I \cup S_O \cup S_E$:

$$ \text{STH}_{\{S_I, S_O\}}(s_i, s_j) = \begin{cases} \text{?}(\text{undefined}) & \text{if } \forall i \in \mathcal{I}_{ij}, \sigma_i^t \in S_E \text{ or } \sigma_j^t \in S_E \\ 1 & \text{if } \forall i \in \mathcal{I}_{ij}, \sigma_i^t \notin S_I \text{ and } \sigma_j^t \notin S_I \\ x(s_i, s_j) & \text{otherwise} \end{cases} \quad (1) $$

with

$$ x(s_i, s_j) = \frac{\sum_{i \in \mathcal{I}_{ij}} |\sigma_i^t - \sigma_j^t| \Delta_i}{\sum_{i \in \mathcal{I}_{ij}} |\sigma_i^t - \sigma_j^t| (S_I^2 \cup (S_I \times S_O) \cup (S_O \times S_I))} \quad (2) $$

The Selective Temporal Hamming distance $STHD$ is defined when $STH$ is defined, as

$$ \text{STHD}_{\{S_I, S_O\}}(s_i, s_j) = 1 - \text{STH}_{\{S_I, S_O\}}(s_i, s_j) \quad (3) $$
## 1.2 Properties

We remind the four core properties of metrics [1]:

1. $d(x, y) \ge 0$ (nonnegativity)

2. $d(x, y) = d(y, x)$ (symmetry)

3. $d(x, y) = 0 \iff x = y$ (distinguishability)

4. $d(x, y) \le d(x, z) + d(z, y)$ (triangle inequality)

**Lemma 1.** *When defined, STHD complies with the nonnegativity property, and its maximum value is 1.*

*Proof.* Durations $\Delta_t$ are $\ge 0$, and the numerator in (2) is included in the denominator, so $0 \le STH \le 1$ and $0 \le STHD \le 1$.

**Lemma 2.** *When defined, STHD complies with the symmetry property.*

*Proof.* All terms in the definition of STH are symmetric.

**Lemma 3.** *When defined, STHD complies with the distinguishability property if and only if $|S_O| \le 1$ and $S_E = \emptyset$.*

*Proof.* Let us first prove that $s_i = s_j \Rightarrow STHD(s_i, s_j) = 0$. If we note $s = s_i = s_j$:

- when $s$ has no values in $S_I$, $STH(s, s) = 1$ by definition (1)

- when $s$ has at least one value in $S_I$, the denominator in (2) is equal to the numerator so $STH(s, s) = 1$.

Now focusing on the reverse implication, we note that $STH(s_i, s_j) = 1$ can only happen in two situations. In both, $S_E = \emptyset$ and $|S_O| \le 1$ are necessary to imply $s_i = s_j$:

- **denominator in (2) is not zero**, and is equal to the numerator. This implies that $\forall l \in I_{ij}$, either $\sigma_i^l = \sigma_j^l$ (and $\sigma_i^l \in S_I$), or we are in a situation that is not in the denominator so $\sigma_i^l \in S_E$ or $\sigma_j^l \in S_E$ or $(\sigma_i^l, \sigma_j^l) \in S_O^2$. So $S_E = \emptyset$ and $|S_O| \le 1$ are necessary to remove all ambiguous situations and have $s_i = s_j$. A proof by contradiction:

* If $S_E$ is not empty, we note that replacing any value $\sigma_i^l$ by a state in $S_E$ simply removes $l$ from both the numerator and denominator sums. Therefore $STH$ remains at 1, but the series are now different.

* If $|S_O| > 1$ we can have one interval $l$ where $s_i$ and $s_j$ have distinct values in $S_O$. This interval disappears from both the numerator and denominator sums, therefore $STH$ remains at 1, but the series are now different.

- **denominator in (2) is zero.** In this situation, $STH = 1$ "by definition" (1). This can happen if $\forall l \in I_{ij}$, either $\sigma_i^l \in S_E$ or $\sigma_j^l \in S_E$ or $(\sigma_i^l, \sigma_j^l) \in S_O^2$ - in other words, all intervals are in a situation that is not in the denominator. The necessary conditions for $s_i = s_j$ are therefore the same as in the above.
## 2 Proof of triangular inequality

**Lemma 4.** When defined, STHD complies with the triangular inequality property if $S_E = \emptyset$.

*Proof.* (the "general case" part of the proof below is inspired by the simple proof of triangular inequality for the Jaccard index provided by [2]).

We consider three categorical timeseries $s_i$, $s_j$, $s_l$. Since $S_E = \emptyset$, they can have values in $S_I$ or $S_O$ only. Equation (2) can be used, except when both series to compare have all their values in $S_O$. We first show that the triangular inequality holds for these specific situations:

- when $s_i$, $s_j$ and $s_l$ have all their values in $S_O$, $STHD(s_i, s_j) = STHD(s_j, s_l) = STHD(s_i, s_l) = 0$ from (1)

- when only 2 series (say, $s_i$ and $s_j$) have all values in $S_O$ and the other ($s_l$) has at least one value in $S_I$, then $STHD(s_i, s_j) = 0$ from (1) and $STHD(s_i, s_l) = STHD(s_j, s_l) = 0$ from (2).

We now address the general case where at least two series in $s_i$, $s_j$ and $s_l$ have at least one value in $S_I$: thus, (2) can be used to compute $STH$ for any pair. We first observe that the sums in (2) can be written on any subdivision of intervals. We therefore consider the collection $\mathcal{I}_{ijl} = \{\iota_k\}$ of time intervals defined by the union of all timestamps in $s_i$, $s_j$ and $s_l$. We note $\Delta_{ABC}$ the cumulated duration of all intervals $\iota$ in $\mathcal{I}_{ijl}$ where $\sigma_i^l \in A$, $\sigma_j^l \in B$ and $\sigma_l^l \in C$. For example $\Delta_{IOI}$ refers to all intervals where $s_i$ and $s_l$ have a value in $S_I$ while $s_j$ has a value in $S_O$.

$$T = \Delta_{III} + \Delta_{OOO} + \Delta_{IOO} + \Delta_{OII} + \Delta_{OIO} + \Delta_{IOI} + \Delta_{OOI} + \Delta_{IIIO} \quad (4)$$

We further partition $\Delta_{III}$ into five durations: $\Delta_{I \neq}$ (when $s_i$, $s_j$ and $s_l$ have different values in $S_I$), $\Delta_{Ii=j=l}$ (when $s_i$, $s_j$ and $s_l$ have the same value in $S_I$), and the three durations where only two series have the same value in $S_I \Delta_{Ii=j \neq l}$, $\Delta_{Ij=l \neq i}$, and $\Delta_{Ii=l \neq j}$. So,

$$\Delta_{III} = \Delta_{Ii=j=l} + \Delta_{I \neq} + \Delta_{Ii=j \neq l} + \Delta_{Ij=l \neq i} + \Delta_{Ii=l \neq j} \quad (5)$$

Finally, we decompose $\Delta_{IOI}$, $\Delta_{OII}$ and $\Delta_{IOI}$ into the duration where the pair in $S_I$ has equal value, and the duration where the pair in $S_I$ has distinct value:

$$\Delta_{IIIO} = \Delta_{Ii=jO} + \Delta_{Ii \neq jO} \quad (6)$$

$$\Delta_{OII} = \Delta_{Ij=lO} + \Delta_{Ij \neq lO} \quad (7)$$

$$\Delta_{IOI} = \Delta_{Ii=lO} + \Delta_{Ii \neq lO} \quad (8)$$
We can rewrite (2) according to this new notation:

$$ 
\begin{aligned}
STH(s_i, s_j) &= \frac{\Delta_{Ii=j \neq l} + \Delta_{Ii=j=l} + \Delta_{Ii=jO}}{\Delta_{III} + \Delta_{IIO} + \Delta_{IOI} + \Delta_{IOO} + \Delta_{OII} + \Delta_{OIO}} \\
STH(s_i, s_j) &= \frac{\Delta_{Ii=j \neq l} + \Delta_{Ii=j=l} + \Delta_{Ii=jO}}{T - \Delta_{OOI} - \Delta_{OOO}}
\end{aligned}
\qquad (9) $$

From its definition (3), STHD therefore writes

$$ STHD(s_i, s_j) = \frac{T - \Delta_{OOI} - \Delta_{OOO} - \Delta_{Ii=j \neq l} - \Delta_{Ii=j=l} - \Delta_{Ii=jO}}{T - \Delta_{OOI} - \Delta_{OOO}} \qquad (10) $$

we can lower bound it by adding $\Delta_{OOI}$ (which is positive) to the denominator:

$$ STHD(s_i, s_j) \geq \frac{T - \Delta_{OOI} - \Delta_{OOO} - \Delta_{Ii=j \neq l} - \Delta_{Ii=j=l} - \Delta_{Ii=jO}}{T - \Delta_{OOO}} \qquad (11) $$

Now let's sum (11) for two pairs:

$$ STHD(s_i, s_j) + STHD(s_j, s_i) \geq \frac{n(i, j, l)}{T - \Delta_{OOO}} \qquad (12) $$

with

$$ n(i, j, l) = (T - \Delta_{OOI} - \Delta_{OOO} - \Delta_{Ii=j \neq l} - \Delta_{Ii=j=l} - \Delta_{Ii=jO}) + (T - \Delta_{IOO} - \Delta_{OOO} - \Delta_{Ij=l \neq i} - \Delta_{Ii=j=l} - \Delta_{Ij=lO}) \qquad (13) $$

we simplify thanks to (4) (5), (6), and (7):

$$ n(i, j, l) = (T - \Delta_{OOO} - \Delta_{Ii=j=l}) + (\Delta_{OIO} + \Delta_{IOI} + \Delta_{I \neq} + \Delta_{Ii=l \neq j} + \Delta_{Ii \neq jO} + \Delta_{Ij \neq lO}) $$

Since the second group is a positive term we can subtract it to get a lower bound

$$ n(i, j, l) \geq (T - \Delta_{OOO}) - \Delta_{Ii=j=l} \qquad (14) $$

And finally
$$STHD(s_i, s_j) + STHD(s_j, s_l) \ge 1 - \frac{\Delta_{Ii=j=l}}{T - \Delta_{OOO}} \quad (15)$$

Now lets consider $STHD(s_i, s_l)$:

$$STHD(s_i, s_l) = 1 - \frac{\Delta_{Ii=l \neq l} + \Delta_{Ii=j=l} + \Delta_{Ii=jO}}{T - \Delta_{OIO} - \Delta_{OOO}} \quad (16)$$

$$STHD(s_i, s_l) \le 1 - \frac{\Delta_{Ii=l \neq l} + \Delta_{Ii=j=l} + \Delta_{Ii=jO}}{T - \Delta_{OOO}} \quad (17)$$

$$STHD(s_i, s_l) \le 1 - \frac{\Delta_{Ii=j=l}}{T - \Delta_{OOO}} \quad (18)$$

Combining equations (15) and (18) proves the triangular inequality.

## References

1. Deza, M.M., Deza, E.: Encyclopedia of Distances. Springer, Berlin (2009). https://doi.org/10.1007/978-3-642-00234-2_1

2. Gilbert, G.: Distance between Sets. Nature 239(5368), 174 (Sep 1972). https://doi.org/10.1038/239174c0

3. Marié, S., Knecht, P.: A Selective Temporal Hamming distance to find patterns in state transition event timeseries, as scale. In: 1st International Conference on Big Data Analytics and Applications (BDAA). Innsbruck, Austria (Nov 2025)