# A Boundary Distance-Based Symbolic Aggregate Approximation Method for Time Series Data
## 3 SAX-BD: Boundary Distance-Based Method For Time Series
### Lower Bound  
One of the most important characteristics of the SAX is that it provides a lower bounding distance measure. Lower bound is very useful for controlling errors and speeding up the computation. Below, we will show that our proposed distance also lower bounds the Euclidean distance.  
According to [19; 20], we have proved that the PAA distance lower bounds the Euclidean distance as follows:  
\[\sqrt{\sum_{i=1}^{n}(q_{i}-c_{i})^{2}}\geq\sqrt{\frac{n}{w}}\quad\sqrt{\sum_{i =1}^{w}\left(\overline{q_{i}},\overline{c_{i}}\right)^{2}} \tag{15}\]  
Figure 5: Time series represented as ‘adfeeffcaeffffdaabc’ by ESAX [25]. Where the length of time series is 30, the number of segments is 6 and the size of symbols is 6. The capital letters A–H represent the maximum and minimum values in every segment.  
For proving the TDIST also lower bounds the Euclidean distance, we repeat some of the proofs here. Let Q and C be the means of time series Q and C respectively. We first consider only the single frame case (i.e., \(w=1\)), Equation (14) can be rewritten as follows:  
\[\sum_{i=1}^{n}(q_{i}-c_{i})^{2}\geq n\Big{(}\overline{Q}-\overline{C}\Big{)}^{2} \tag{16}\]  
Recall that Q is the average of the time series, so \(q_{i}\) can be represented in terms of \(q_{i}=\overline{Q}-\Delta q_{i}\). The same applies to each point \(c_{i}\) in C, Equation (15) can be rewritten as follows:  
\[n\Big{(}\overline{Q}-\overline{C}\Big{)}^{2}+\sum_{i=1}^{n}\left(\Delta q_{i} -\Delta c_{i}\right)^{2}\geq n\Big{(}\overline{Q}-\overline{C}\Big{)}^{2} \tag{17}\]  
Because \(\sum\limits_{i=1}^{n}\left(\Delta q_{i}-\Delta c_{i}\right)^{2}\geq 0\), Recall the definition in Equation (9) and Equation (12), \(\left(\Delta q(t)_{1}-\Delta C(t)_{1}\right)^{2}+\left(\Delta q(t)_{2}-\Delta C (t)_{2}\right)^{2}\), we can obtain an inequality as follows (its' obviously exists that the boundary distance in \(\Delta q_{i}\)):  
\[\sum_{i=1}^{n}(q_{i}-c_{i})^{2}\geq\left(\Delta q(t)_{1}-\Delta C(t)_{1} \right)^{2}+\left(\Delta q(t)_{2}-\Delta C(t)_{2}\right)^{2} \tag{18}\]  
Substituting Equation (16) into Equation (17), we get:  
\[n\Big{(}\overline{Q}-\overline{C}\Big{)}^{2}+\sum_{i=1}^{n}(q_{i}-c_{i})^{2} \geq n\Big{(}\overline{Q}-\overline{C}\Big{)}^{2}+\left(bd(q_{i},c_{i})\right) ^{2} \tag{19}\]  
According to [20], the MINDIST lower bounds the PAA distance, that is:  
\[n\Big{(}\overline{Q}-\overline{C}\Big{)}^{2}\geq n\Big{(}\hat{Q}-\hat{C} \Big{)}^{2} \tag{20}\]  
where \(\hat{Q}\) and \(\hat{C}\) are symbolic representations of Q and C in the original SAX, respectively. By transitivity, the following inequality is true  
\[\Big{(}\overline{Q}-\overline{C}\Big{)}^{2}+\sum_{i=1}^{n}\left(\Delta q_{i} -\Delta c_{i}\right)^{2}\geq n\Big{(}dist\Big{(}\hat{Q}-\hat{C}\Big{)}\Big{)} ^{2}+\left(bd(q_{i},c_{i})\right)^{2} \tag{21}\]  
Recall Equation (15), this means  
\[\sum_{i=1}^{n}\left(\Delta q_{i}-\Delta c_{i}\right)^{2}\geq n\Big{(}\Big{(} dist\Big{(}\hat{Q}-\hat{C}\Big{)}\Big{)}^{2}+\frac{1}{n}\left(bd(q_{i},c_{i}) \right)^{2}\Big{)} \tag{22}\]  
\(N\) frames can be obtained by applying the single-frame proof on every frame, that is  
\[\sqrt{\sum_{i=1}^{n}(q_{i}-c_{i})^{2}}\geq\sqrt{\frac{n}{w}}\ \sqrt{\sum_{i=1}^{w}(( dist(\hat{q},\hat{c}))^{2}+\frac{w}{n}\left(bd(q_{i},c_{i})\right)^{2}} \tag{23}\]  
The quality of a lower bounding distance is usually measured by the tightness of lower bounding (TLB).  
\[TL=\frac{Lower\ Bounding\ Distance(Q,C)}{Euclidean\ Distance(Q,C)}\]The value of TLB is in the range [0, 1]. The larger the TLB value, the better the quality. Recall the distance measure in Equation (13), we can obtain that \(TLB(BDIST)\geq TLB(MINIDIST)\) which means the SAX-BD distance has a tighter lower bound than the original SAX distance.