Time Series Compression Survey

4.1.1 TRISTAN.

One implementation of the DB architecture is TRISTAN [7], an algorithm divided into two phases: the learning phase and the compression phase.

Learning phase. The dictionary used in this implementation can be created by domain experts that add typical patterns or by learning a training set. To learn a dictionary from a training set \(T = [t_1, \dots , t_n]\) of \(n\) segments, the following minimization problem has to be solved: (5) \(\begin{equation} \begin{split} D = \arg \underset{D}{\min }\sum _{i = 1}^{n}{\Vert w_i D - t_i\Vert _2}. \\ \text{Under the constraint:}\ \Vert w_i\Vert _0 \le sp, \end{split} \end{equation}\)

where \(D\) is the obtained dictionary, \(sp\) is a fixed parameter representing sparsity, \(w_i\) is the compressed representation of segment \(i\), and \(w_i D\) is the reconstructed segment. The meaning of this formulation is that the solution to be found is a dictionary that minimizes the distance between original and reconstructed segments.

The problem shown in Equation (5) is NP-hard [7], thus an approximate result is computed. A technique for approximating this result is shown in [8].

Compression phase. Once the dictionary is built, the compression phase consists in finding \(w\) such that: (6) \(\begin{equation} s = w\cdot D, \end{equation}\) where \(D\) is the dictionary, \(s\) is a segment and \(w \in \lbrace 0,1\rbrace ^k\), and \(k\) is the length of the compressed representation. An element of \(w\) in position \(i\) is 1 if the \(a_i \in D\) is used to reconstruct the original segment, 0 otherwise.

Finding a solution for Equation (6) is an NP-hard problem and, for this reason, the matching pursuit method [9] is used to approximate the original problem: (7) \(\begin{equation} \begin{split} \overline{s} = \underset{w}{\arg }\min \Vert wD - s\Vert _2. \\ \text{Under the constraint:}\ \Vert \overline{s}\Vert _0\le sp, \end{split} \end{equation}\)

where \(sp\) is a fixed parameter representing sparsity.

Reconstruction phase. Having a dictionary \(D\) and a compressed representation \(w\) of a segment \(s\), it is possible to compute \(\overline{s}\) as (8) \(\begin{equation} \overline{s} = wD . \end{equation}\)

4.1.2 CORAD.

This implementation extends the idea presented in TRISTAN [10]. The main difference is that it adds autocorrelation information to get better performances in terms of compression ratio and accuracy.

Correlation between two time series \(TS^A\) and \(TS^B\) is measured with the Pearson correlation coefficient: (9) \(\begin{equation} r = \frac{\sum _i^n(x_i-\overline{x})(y_i-\overline{y})}{\sqrt {\sum _i^n(x_i-\overline{x})^2}\sqrt {\sum _i^n(y_i - \overline{y})^2}}, \end{equation}\) where \(x_i\) is an element of \(TS^A_n\), \(y_i\) is an element of \(TS^B_n\) and \(\overline{x},\overline{y}\) are mean values of the corresponding time series. This coefficient can be applied also to segments that have different ranges of values and \(r \in [-1, q]\) where 1 expresses the maximum linear correlation, \(-\)1 the maximum linear negative correlation, and 0 no linear correlation.

Time series are divided into segments and time windows are set. For each window, correlation is computed between each segment belonging to it, and results are stored in a correlation matrix \(M\in \mathbb {R}^{n \times n}\) where \(n\) is the segment number of elements.

Compression phase. During this phase, segments are sorted from the less correlated to the most correlated. To do this, a correlation matrix \(M\) is used. The metric used to measure how much one segment is correlated with all the others is the absolute sum of the correlations, computed as the sum of each row of \(M\).

Knowing correlation information, a dictionary is used only to represent segments that are not correlated with others, as in TRISTAN implementation. While the other segments are represented solely using correlation information.

Reconstruction phase. The reconstruction phase starts with the segment represented with dictionary atoms while the others are reconstructed looking at the segment to which they are correlated.

This process is very similar to the one proposed in TRISTAN, with the sole difference that segments represented in the dictionary are managed differently than those that are not.

4.1.3 Accelerometer LZSS (A-LZSS).

A-LZSS is an algorithm built on top of the LZSS algorithm [11] for searching matches [12]. A-LZSS algorithm uses Huffman codes, generated offline using frequency distributions. In particular, this technique considers blocks of size \(s=1\) to compute frequencies and build the code: an element of the time series will be replaced by a variable number of bits. Moreover, larger blocks can be considered and, in general, having larger blocks gives better compression performances at the cost of larger Huffman code tables.

The implementation of this technique is shown in Algorithm 3, where:

This implementation uses a brute-force approach, with complexity \(O(2^{Dn}\cdot 2^{Ln})\) but it is possible to improve it by using hashing techniques.

4.1.4 Differential LZW (D-LZW).

The core of this technique is the creation of a very large dictionary that grows over time: once the dictionary is created, if a buffer block is found inside the dictionary it is replaced by the corresponding index, otherwise, the new block is inserted in the dictionary as a new entry [13].

Adding new blocks guarantees lossless compression, but has the drawback of having too large dictionaries. This makes the technique suitable only for particular scenarios (i.e, input streams composed of words/characters or when the values inside a block are quantized).

Another drawback of this technique is how the dictionary is constructed: elements are simply appended to the dictionary to preserve the indexing of previous blocks. For a simple implementation of the dictionary, the complexity for each search is \(O(n)\) where \(n\) is the size of the dictionary. This complexity can be improved by using more efficient data structures.

4.2.1 Piecewise Polynomial Approximation (PPA).

This technique divides a time series into several segments of fixed or variable length and tries to find the best polynomials that approximate segments.

Despite the compression is lossy, a maximum deviation from the original data can be fixed a priori to enforce a given reconstruction accuracy.

The implementation of this algorithm is described in [14] where the authors apply a greedy approach and three different online regression algorithms for approximating constant functions, straight lines, and polynomials. These online algorithms are

The algorithm used in [14] for approximating a time series segment is explained in Algorithm 4.

This algorithm finds repeatedly the polynomial of degree between 0 and a fixed maximum that can approximate the longest segment within the threshold error, yielding the maximum local compression factor. After a prefix of the stream has been selected and compressed into a polynomial, the algorithm analyzes the following stream segment. A higher value of \(\epsilon\) returns higher compression and lower reconstruction accuracy. The fixed maximum polynomial degree \(\rho\) affects compression speed, accuracy, and compression ratio: higher values slow down compression and reduce the compression factor, but return higher reconstruction accuracy.

4.2.2 Chebyshev Polynomial Transform (CPT).

Another implementation of polynomial compression can be found in [18]. In this article, the authors show how a time series can be compressed in a sequence of finite Chebyshev polynomials.

The principle is very similar to the one shown in Section 4.2.1 but based on the use of a different type of polynomial. Chebyshev Polynomials are of two types, \(T_n(x)\), \(U_n(x)\), defined as [19]: (10) \(\begin{align} T_n(x) = \frac{n}{2}\sum _{k=0}^{n / 2}(-1)^k\frac{(n-k-1)!}{k!(n-2k)!}(2x)^{n-2k}, |x|\lt 1, \end{align}\) (11) \(\begin{align} U_n(x) = \sum _{k=0}^{n/2}(-1)^k\frac{(n-k)!}{k!(n-2k)!}(2x)^{n-2k}, |x|\lt 1, \end{align}\) where \(n \ge 0\) is the polynomial degree.

4.2.3 Discrete Wavelet Transform (DWT).

DWT uses wavelet functions to transform time series. Wavelets are functions that, similarly to a wave, start from zero, and end with zero after some oscillation. An application of this technique can be found in [20].

This transformation can be written as (12) \(\begin{equation} \Psi _{m,n}(t) = \frac{1}{\sqrt {a^m}}\Psi \left(\frac{t - nb}{a^m}\right), \end{equation}\) where \(a \gt 1\), \(b \gt 0\), \(m,n\in Z\).

To recover one transformed signal, the following formula can be applied: (13) \(\begin{equation} x(t) = \sum _{m\in {Z}}\sum _{n\in {Z}}\langle x, \Psi _{m,n}\rangle \cdot \Psi _{m,n}(t). \end{equation}\)

4.2.4 Discrete Fourier Transform (DFT).

Together with the DWT, the DFT is commonly used for signal compression. Given a time series \([(t_1, x_1), \dots , (t_n, x_n)]\), it is defined as \(\begin{equation*} X_k = \sum ^{N}_{n=1} x_n e^{\frac{-i2\pi kn}{N}}. \end{equation*}\)

Where \(e^{\frac{i2\pi }{N}}\) is a primitive \(N\)th root of 1.

To efficiently compute this transformation, the Fast Fourier transform algorithm can be used, as the one introduced here [42]. As described in [43], compressing a time series can be done after applying the DFT by cutting coefficients that are close to zero. This can be done also by fixing a compression ratio and discarding all the coefficients after a certain index.

4.2.5 Discrete Cosine Transform (DCT).

Given a time series \([(t_1, x_1), \dots , (t_n, x_n)]\), the DCT is defined as \(\begin{equation*} c_k = \sum ^{N}_{n=0} x_n \cdot \text{cos} \left[\frac{\pi }{N}\left(n + \frac{1}{2}\right)k\right]. \end{equation*}\)

The computation of this transformation is computationally expensive, so efficient implementations can be used, as the one presented in [44].

Similarly to the DFT, compression of time series can be achieved by cutting the coefficients that are close to zero or by fixing a compression ratio and discarding all the coefficients after a certain index. An example of this technique can be found in [45].

4.3.1 Recurrent Neural Network Autoencoder (RNNA).

RNNA compression algorithms exploit recurrent neural networks [22] to achieve a compressed representation of a time series. Figure 5 shows the general unrolled structure of a recurrent neural network encoder and decoder. The encoder takes in input time series elements, which are combined with hidden states. Each hidden state is then computed starting from the new input and the previous state. The last hidden state of the encoder is passed as the first hidden state of the decoder, which applies the same mechanism, with the only difference being that each hidden state provides an output. The output provided by each state is the reconstruction of the relative time series element and is passed to the next state.

Fig. 5.

View Figure

New hidden state \(h_t\) is obtained by applying: (14) \(\begin{equation} h_t = \phi (Wx_t+Uh_{t-1}), \end{equation}\) where \(\phi\) is a logistic sigmoid function or the hyperbolic tangent.

One application of this technique is shown in [23], in which also Long Short-Term Memory [24] is considered. This implementation compresses time series segments of different lengths using autoencoders. The compression achieved is lossy and a maximal loss threshold \(\epsilon\) can be enforced.

The training set is preprocessed considering temporal variations of data applying: (15) \(\begin{equation} \Delta (\mathcal {L}) = \sum _{t \in \mathcal {L}}|x_t-x_{t-1}|, \end{equation}\) where \(\mathcal {L}\) is the local time window.

The value obtained by Equation (15) is then used to partition the time series, such that each segment has a total variation close to a predetermined value \(\tau\).

Algorithm 5 shows an implementation of the RNN autoencoder approach, with an error threshold \(\epsilon\), where:

4.3.2 Recurrent Convolutional Autoencoder (RCA).

A variation of the technique presented in the previous subsection is proposed in [49] and consists of adding convolutional layers. Convolutional layers are used mainly for images data to extract local features. In the case of time series, this layer allows extracting local fluctuations and addressing complex inputs.

4.3.3 DZip.

DZip is a lossless recurrent autoencoder [47]. This model also uses the prediction technique: it tries to predict the next symbol, having, in this case, a fixed vocabulary. To achieve a lossless compression, it combines two modules: the bootstrap model and the supporter model, as shown in Figure 6.

Fig. 6.

View Figure

The bootstrap model is composed by stacking two bidirectional gated recurrent units, followed by linear and dense layers. The output of this module is a probability distribution, that is, the probability of each symbol in the fixed vocabulary to be the next one.

The supporter model is used to better estimate the probability distribution with respect to the bootstrap model. It is composed by stacking three neural networks which act as independent predictors of varying complexity.

The two models are then combined by applying the following equation: \(\begin{equation*} o = \lambda o_{b} + (1 - \lambda) o_s. \end{equation*}\)

Where \(o_b\) is the output of the bootstrap model, \(o_s\) is the output of the supporter model, and \(\lambda \in [0, 1]\) is a learnable parameter.

4.4.1 Delta Encoding, Run-length, and Huffman (DRH).

This technique combines together three well-known compression techniques [28]: delta encoding, run-length encoding, and Huffman code. Since these techniques are all lossless, the compression provided by DRH is lossless too if no quantization is applied.

Algorithm 7 describes the compression algorithm, where \(Q\) is the quantization level and is asserted to be \(\ge\)1: if \(Q = 1\) the compression is lossless, and increasing values of \(Q\) return a higher compression factor and lower reconstruction accuracy.

The decompression algorithm is the inverse of the compression one: once data is received, it is decoded using the Huffman code and reconstructed using the repetition counter.

Since this kind of algorithm is not computationally expensive, the compression phase can be performed also by low-resource computational units, such as sensor nodes.

4.4.2 Sprintz.

Sprintz algorithm [29] is designed for the IoT scenario, in which energy consumption and speed are important factors. In particular, the goal is to satisfy the following requirements:

The proposed algorithm is a coder that exploits prediction to achieve better results. In particular, it is based on the following components:

4.4.3 Run-Length Binary Encoding (RLBE).

This lossless technique is composed of five steps, combining delta encoding, run-length, and Fibonacci coding, as shown in Figure 7 [30].

Fig. 7.

View Figure

This technique is developed specifically for devices characterized by low memory and computational resources, such as IoT infrastructures.

4.4.4 RAKE.

RAKE algorithm, presented in [31], exploits sparsity to achieve compression. It is a lossless compression algorithm with two phases: preprocessing and compression.

Preprocessing. In this phase, a dictionary is used to transform original data. For this purpose, many algorithms can be used, such as the Huffman coding presented in Section 4.4, but since the aim is that of obtaining sparsity, the RAKE dictionary uses a code similar to unary coding thus every codeword has at most one bit set to 1. This dictionary does not depend on symbol probabilities, so no learning phase is needed. Table 1 shows a simple RAKE dictionary.

Compression. This phase works, as suggested by the algorithm name, as a rake of \(n\) teeth. Figure 8 shows an execution of the compression phase, given a preprocessed input and \(n=4\).

Fig. 8.

View Figure

The rake starts at position 0, in case there is no bit set to 1 in the rake interval, then 0 is added to the code, otherwise 1 and followed by the binary representation of relative index for the first bit set to 1 in the rake (2 bits in the example in Figure 8). After that, the rake is shifted right of \(n\) positions for the first case or starting right to the first found bit. In the figure, the rake is initially at position 0, and the first bit set to 1 is in relative position 1 (output: 1 followed by 01), then the rake advances of 2 positions (after the first 1 in the rake); all bits are set to zero (output: 0) thus that rake is moved forward by 4 places; the first bit set to 1 in the rake has relative index 2 (output: 1 followed by 10) thus the rake is advanced by 3 places and the process continues for the two last rake positions (output: 101 and 0, respectively).

Decompression. The decompression processes the compressed bit stream by replacing 0 with \(n\) occurrences of 0 and 1 followed by an offset with a number 0 equal to the offset followed by a bit set to 1. The resulting stream is decoded on the fly using the dictionary.

4.5.1 Major Extrema Extractor (MEE).

This algorithm is introduced in [32] and exploits time series features (maxima and minima) to achieve compression. For this purpose, strict, left, right, and flat extrema are defined. Considering a time series \(TS = [(t_0, x_0), \dots , (t_n,x_n)]\), \(x_i\) is a minimum if it follows these rules:

For maximum points, they are defined similarly.

After defining minimum and maximum extrema, the authors introduce the concept of importance, based on a distance function dist and a compression ratio \(\rho\): \(x_i\) is an important minimum if \(\begin{eqnarray*} \exists i_l \lt i \lt i_r : & x_i \text{ is minimum in}\ \lbrace x_l, \dots , x_r\rbrace \wedge \\ & {\it dist}(x_l, x_i) \lt \rho \wedge {\it dist}(x_i, x_r) \lt r. \end{eqnarray*}\)

Important maximum points are defined similarly.

Once important extrema are found, they are used as a compressed representation of the segment. This technique is a lossy compression technique, as the SM one described in the next section. Although the compressed data can be used to obtain original data properties useful for visual data representation (minimum and maximum), it is impossible to reconstruct the original data.

4.5.2 Segment Merging (SM).

This technique, presented in [48] and reused in [33] and [50], considers time series with regular timestamps and repeatedly replaces sequences of consecutive elements (segments) with a summary consisting of a single value and a representation error, as shown in Figure 9 where the error is omitted.

Fig. 9.

View Figure

After compression, segments are represented by tuples \((t, y, \delta)\) where \(t\) is the starting time of the segment, \(y\) is the constant value associated with the segment, and \(\delta\) is the segment error. The merging operation can be applied either to a set of elements or to a set of segments, to further compress a previously compressed time series. The case of elements is an instance of the case of segments, and it is immediate to generalize from two to more elements/segments. We limit our description to the merge of two consecutive segments represented by the tuples \((t_i, y_i, \delta _i)\) and \((t_j, y_j, \delta _j)\), where \(i \lt j\), into a new segment represented by the tuple \((t, y, \delta)\) computed as \(\begin{gather*} t = t_i, \\ y = \frac{\Delta t_i\cdot y_i + \Delta t_j\cdot y_j}{\Delta t_i + \Delta t_j}, \\ \delta = \sqrt {\frac{\Delta t_i\cdot (y_i^2 + \delta _i^2) + \Delta t_j\cdot (y_i^2 + \delta _i^2)}{\Delta t_i + \Delta t_j}-y^2}, \end{gather*}\) where \(\Delta t_x\) is the duration of the segment \(x\), thus \(\Delta t_i = t_j - t_i\), \(\Delta t_j = t_k - t_j\) and \(t_k\) is the timestamp of the segment after the one starting at \(t_j\).

The sets of consecutive segments to be merged are chosen to minimize segment error with constraints on a maximal acceptable error and maximal segment duration.

This compression technique is lossy and the result of the compression phase can be considered both as the compressed representation and as the reconstruction of the original time series, without any additional computations executed by a decoder.

4.5.3 Continuous Hidden Markov Chain (CHMC).

The idea behind this algorithm is that the data generation process follows a probabilistic model and can be described with a Markov chain [34]. This means that a system can be represented with a set of finite states \(S\) and a set of arcs \(A\) for transition probabilities between states.

Once the hidden Markov chain is found using known techniques, such as the one presented in [35], a lossy reconstruction of the original data can be obtained by following the chain probabilities.

5.1.1 TRISTAN.

Accuracy. The creation of the dictionary depends on the dictionary sparsity parameter that is directly related to its size and the accuracy can be influenced by this value, as shown in Equation (5). Experimental results are shown in Figure 10, where sparsity is related to RMSE.

Fig. 10.

View Figure

Compression ratio. The sparsity parameter also affects the compression ratio. To assess this dependency, the authors execute experiments on two different datasets both containing one measurement per minute with daily segments: RTE and ICDM, using dictionaries consisting respectively of 16 and 131 atoms.

The resulting compression ratios are \(\rho = 0.5\) for RTE and \(\rho = 0.05\) for ICDM, thus higher sparsity values (larger dictionaries) allow for better compression ratios.

5.1.2 CORAD.

Accuracy. The authors of CORAD measure accuracy using MSE and the best-reported results for their algorithms are 0.03 for the BAFU dataset, 0.11 for the GSATM dataset, and 0.04 for the ACSF1 dataset. As for TRISTAN, accuracy depends on time series segments redundancy and correlation.

Compression ratio. The best reported results for CORAD compression ratio are \(\rho =0.04\) for the ACSF1 dataset, \(\rho = 0.07\) for the BAFU dataset and \(\rho = 0.06\) for the GSATM dataset.

The compression ratio is affected by the parameters used during training and encoding: error threshold, sparsity, and segment length. Their effects are depicted in the three plots in Figure 11, which represent the compression factor (\(\frac{1}{\rho }\)) obtained for different values of the parameters.

Fig. 11.

View Figure

5.1.3 A-LZSS.

The compression ratio obtained by the A-LZSS algorithm depends on two parameters: \(L_n\) and \(D_n\), which are respectively the lookahead distance, and the dictionary atoms length. From the experiments conducted by the authors in [12], the best compression ratio is obtained setting \(L_n=5\) and \(D_n=10\). Increasing \(L_n\) and decreasing \(D_n\) penalize this quality index, as values of \(L_n \lt 4\).

5.1.4 D-LZW.

The authors did not provide a detailed study on the compression performances, limiting the experimental results only to EGC and PPG signals. Nevertheless, they did a comparison with Bzip2 and Gzip, giving the results shown in Table 3.

5.1.5 Piecewise Polynomial Approximation (PPA).

Accuracy and compression ratio of PPA are affected by the maximum polynomial degree and the maximum allowed deviation, the parameters of the method as described in Section 4.2.

Accuracy. Errors are bounded by the maximum deviation parameter and the maximum polynomial degree can affect accuracy: deviation is always under the threshold and using higher degree polynomials yield more precise reconstructions.

Figure 12 shows the relation between maximum deviation and MSE.

Fig. 12.

View Figure

Compression ratio. Both the maximum deviation and polynomial degree parameters affect the compression ratio, as we can observe in Figure 13 where the compression factor (\(\frac{1}{\rho }\)) is reported for different values of parameters. The best compression ratios, \(\rho = 0.06\) for REDD and \(\rho = 0.02\) for Office, are achieved for the highest degree polynomials. As expected, also for increasing maximum deviation the compression factor is monotonically increasing.

Fig. 13.

View Figure

5.1.6 Chebyshev Polynomial Transform (CPT).

Despite the absence of experimental results in the original article, some considerations can be done. The algorithm has three parameters:

Similarly to PPA, in CPT it is possible to obtain higher compression ratios at the cost of higher MSE by increasing the maximum deviation parameter. The same holds for the block size: larger blocks correspond to better compression ratios and higher decompression errors [18]. Similarly, we can suppose that using fewer quantization bits would entail a less accurate decompression and a better compression ratio.

5.1.7 Discrete Wavelet Transform (DWT).

As for CPT, experimental results are not provided, but also DWT performances follow the same rules as for PPA since the compression ratio and threshold errors are strictly correlated. The threshold error can be fixed a priori to have a higher compression ratio or a higher accuracy.

5.1.8 Discrete Fourier Transform (DFT).

The authors tested the performance of the DFT algorithm using three types of signals: Block, Heavy Sine, and Mishmash. The compression ratio depends on the percentage of coefficients that are removed. The optimum threshold is derived by iterative tests, and it depends on the signal type. As stated by the authors, the results obtained by DWT are comparable to the ones obtained by DWT: the choice of the algorithm highly depends on the type of signal that has to be compressed [43].

5.1.9 Discrete Cosine Transform (DCT).

The accuracy obtained by this algorithm depends on the chosen compression ratio. The authors used the ARIANE 5 (temperature sensor, and vibration sensor) and AISat temperature sensor for their experiments. The results show that the performances of this algorithm are not homogeneous, as they highly depend on the input dataset. Even if the input data seems to be similar, belonging to the same domain: the performances obtained on the ARIANE 5 and AISat temperature sensors are completely different, as shown in Table 4 [45].

5.1.10 Recurrent Neural Network Autoencoder (RNNA).

Accuracy. One of the parameters of the RNNA-based methods is the threshold for the maximally allowed deviation, whose value directly affects accuracy. For the experiments on UTS presented in [23] the authors report, considering the optimal value for deviation parameter, an RMSE value in the range \([0.02, 0.07]\) for different datasets. In the same experiments, RMSE is in the range \([0.02, 0.05]\) for MTS datasets. Thus, there is no significant difference between univariate and multivariate time series.

Compression ratio. Similarly, the maximally allowed deviation affects the compression ratio. According to the results reported by the authors, in this case, there is not a significant difference between univariate and multivariate time series: \(\rho\) is in the range \([0.01,0.08]\) for the UTS dataset and in the range, \([0.31,0.05]\) for the multivariate one.

5.1.11 Recurrent Convolutional Autoencoder (RCA).

The experimental results reveal a slight improvement with respect to the RNNA model over the traffic flow dataset [49]: without the convolutional layer, the RMSE value is 10.37, while with the convolutional layer, the RMSE decreases to 8.17.

Since the original article is focused on the prediction of the next values only, the compression ratio is missing.

5.1.12 DZip.

The authors tested the model with real and synthetic datasets and compared the results with the state-of-the-art compression algorithms, including RNNA. The results revealed that it outperforms the RNNA autoencoder. The compression ratio depends on the vocabulary size, which is negatively affected by larger sizes. Another factor that influences this parameter is the size of the original data: the larger is the time series to be compressed, the better is the compression ratio [47].

5.1.13 Delta Encoding, Run-Length, and Huffman (DRH).

DRH, as most of the following algorithms, is a lossless algorithm, thus the only relevant performance metric is the compression ratio.

Compression ratio. This parameter highly depends on the dataset: run-length algorithm combined with delta encoding achieves good results if the time series is composed of long segments that are always increasing or decreasing of the same value or constant. Experimental results are obtained on temperature, pressure, and light measures datasets. For this type of data, DRH appears to be appropriate, since the values are not highly variable and have a relatively long interval with constant values. The resulting compression factors are reported in Table 5 [28].

5.1.14 Sprintz.

Compression ratio. This algorithm is tested over the datasets of the UCR time series archive, which contains data coming from different domains. In the boxplots in Figure 14, compression factors are shown for 16 and 8-bit data and compared with other lossless compression algorithms. From this graph, it is possible to see that all algorithms achieve better (higher) compression factors on the 8-bit dataset. This could be due to the fact that 16-bit data are more likely to have higher differences between consecutive values.

Fig. 14.

View Figure

Another interesting result is that the FIRE forecasting technique improves this compression, especially if combined with Huffman coding when compared with Delta coding [29].

5.1.15 Run-Length Binary Encoding (RLBE).

Compression ratio. The author of this algorithm in [30] report compression ratio and processing time of RLBE with respect to those of other algorithms as shown in Figure 15 where ellipses represent the inter-quartile range of compression ratios and processing times. RLBE achieves good compression ratios with a 10% variability and with low processing time.

Fig. 15.

View Figure

5.1.16 RAKE.

Compression ratio. The authors of RAKE in [31] run experiments on sparse time series with different sparsity ratios \(p\) and different algorithms. The corresponding compression factors are reported in Table 6.

We can notice that the compression factor is highly dependent on sparsity and lower sparsity values correspond to higher compression factors (better compression). Thus, the RAKE algorithm is more suitable for sparse time series.

5.1.17 Major Extrema Extractor (MEE).

The compression ratio is one of the parameters of the MEE algorithm, thus the only relevant performance metric is the accuracy.

Accuracy. Even though MEE is a lossy compression algorithm, the authors have not provided any information about accuracy. Since the accuracy depends on the compression ratio, the authors recommend choosing a value that is not smaller than the percentage of non-extremal points, to obtain an accurate reconstruction of the compressed data [32].

5.1.18 Segment Merging (SM).

Since this algorithm is used for visualization purposes, a first evaluation can be a qualitative observation. In Figure 9, we can see how a light sensor time series is compressed considering different time series segment lengths. For this algorithm, compression ratio and error are strictly correlated, as shown in Figure 16 where FWC and CB-\(m\) correspond to different versions of the algorithm and different parameters [33]. We can observe that compression ratio values close to 1 correspond to error values close to zero.

Fig. 16.

View Figure

The dependence of compression ratio and error changes for different datasets. Knowing the function that correlates the compression ratio and error for a given dataset, it is possible to set the compression ratio that corresponds to the desired maximum compression error.

5.1.19 Continuous Hidden Markov Chain (CHMC).

For this algorithm, the authors have not provided any quantitative evaluation for compression performances: their assessment is qualitative and mainly focused on the compression and reconstruction of humanoid robot motions after a learning phase [34].

5.2.1 Dictionary-based.

The DB approaches include both lossy and lossless compression. The compression ratio depends on the atom’s size in the dictionary and on the dataset’s repetitiveness. For large datasets, the storage needed for the dictionary can be considered irrelevant, while for smaller datasets it can be inefficient. The training phase can be inefficient for databases with low repetitiveness.

5.2.2 Functional Approximation.

FA includes only lossy techniques. The compression ratio can be set in advance, as the maximum reconstruction error. They work better with regular data with low fluctuations and peaks.

5.2.3 Autoencoders.

Autoencoders include lossy and lossless techniques. The error threshold can be set in advance, while the compression ratio depends on the quality of the training phase and on the regularity of the dataset. If the autoencoder receives data with different seasonability and distribution with respect to the ones found in the training set, its prediction capacity becomes low. A weak point is the computational cost of the training set: recurrent neural networks are more expensive to be trained respect to classic neural network autoencoders and need a large amount of data in the training set.

5.2.4 Sequential Algorithms.

The selected techniques in this group include lossless techniques only. The compression ratio depends on the data sparsity and regularity, especially for those that use delta and run-length encoding. They do not need a training phase and work well with low-computational resources.

5.2.5 Others.

This group includes lossy techniques, and their peculiarities depend on the single technique.