PaperlayerView exact revision on arXiv

Source-linked AI summary

Time series compression: a survey

Giacomo Chiarot, Claudio Silvestri

arXiv:2101.08784v2cs.DB

TL;DR

Large volumes of time-series data make efficient compression relevant, yet prior surveys did not exhaustively cover time-series techniques. This paper surveys those techniques, organizes them in a taxonomy, and synthesizes reported performance; it concludes that technique suitability depends on time-series characteristics, compression constraints, and purpose.

  • Problem

    Time-series data volumes motivate efficient compression, but prior surveys covered particular domains or compression types rather than exhaustively surveying time-series methods.

    Source: §1 · p. 1, §2.1 · p. 3

  • Method

    The paper surveys time-series compression techniques, classifies them by approach and properties, and recapitulates performance measurements reported in the original studies.

    Source: §1 · p. 2

  • Results

    The most appropriate technique depends on time-series characteristics, compression constraints, and purpose.

    Source: §6 · p. 26

  • Takeaways & Limitations

    The survey’s synthesis can inform technique selection for contexts with particular dataset characteristics or required compression ratios or accuracy.

    Source: §6 · p. 26

    For Major Extrema Extractor, the original authors provided no accuracy information, and the compressed representation cannot reconstruct the original data.

    Source: §4.5.1 · p. 15, §5.1.17 · p. 25

Abstract

from arXiv · show

The presence of smart objects is increasingly widespread and their ecosystem, also known as Internet of Things, is relevant in many different application scenarios. The huge amount of temporally annotated data produced by these smart devices demand for efficient techniques for transfer and storage of time series data. Compression techniques play an important role toward this goal and, despite the fact that standard compression methods could be used with some benefit, there exist several ones that specifically address the case of time series by exploiting their peculiarities to achieve a more effective compression and a more accurate decompression in the case of lossy compression techniques. This paper provides a state-of-the-art survey of the principal time series compression techniques, proposing a taxonomy to classify them considering their overall approach and their characteristics. Furthermore, we analyze the performances of the selected algorithms by discussing and comparing the experimental results that where provided in the original articles. The goal of this paper is to provide a comprehensive and homogeneous reconstruction of the state-of-the-art which is currently fragmented across many papers that use different notations and where the proposed methods are not organized according to a classification.

1 INTRODUCTION

The survey addresses the fragmented state of time-series compression research by organizing techniques developed for or effective on time series. It introduces a taxonomy and summarizes performance measurements reported in the original studies.

1 INTRODUCTION

  • IoT devices produce large volumes of time-series data, making compression relevant to the efficiency of data collection, storage, and analysis.The introduction notes that a single Boeing 787 flight can produce about half a terabyte of sensor data.Source: §1 · p. 1
  • The survey organizes time-series compression techniques by approach and properties, including dictionary-based, functional approximation, autoencoder, and sequential methods.The taxonomy also covers adaptiveness, lossless reconstruction, symmetry, and tuneability of maximum error or minimum compression ratio.Source: §1 · p. 2

1.1 Outline of the Survey

  • The survey summarizes performance measurements reported in the original studies and presents the paper’s structure across literature selection, background, algorithms, results, and conclusions.The algorithms section follows the proposed taxonomy.Source: §1 · p. 2, §1.1 · p. 2

2 LITERATURE SELECTION

The paper responds to the lack of an exhaustive survey of time-series compression and describes how it selected literature. Its scope emphasizes techniques whose compressed representations can reconstruct the original data with reasonably small or zero error.

2.1 Background and Motivation

  • The authors report that earlier compression surveys addressed particular domains or compression types, but none exhaustively covered time series.Source: §2.1 · p. 3

2.2 Literature Selection

  • The literature search found 2,097 ACM Digital Library records using a title query, followed by relevance screening and additional papers selected through snowballing or recent publication in relevant venues.Source: §2.2 · p. 3

2.3 Scope

  • The survey focuses on dimensionality-reduction techniques that allow reconstruction of the original data with reasonably small or zero error.It distinguishes these from techniques not designed to keep reconstruction error reasonably small.Source: §2.3 · p. 3

3 BACKGROUND

The background defines time series and compression, then introduces the properties used to characterize compression algorithms. It also identifies compression ratio, speed, and accuracy as performance characteristics.

3.1 Time series

  • A time series is timestamp-ordered data; univariate series contain real values, while multivariate series contain arrays of real-valued features.The paper also describes segments as ordered portions without missing elements.Source: §3.1 · p. 3

3.2 Compression

  • Compression converts a time series into a smaller representation from which a decoder attempts to reconstruct the original; exact reconstruction distinguishes lossless from lossy compression.Algorithms are also characterized as adaptive or non-adaptive and symmetric or non-symmetric.Source: §3.2 · p. 4

3.3 Quality indices

  • Compression performance is considered in terms of compression ratio, speed, and accuracy, with accuracy also called distortion.The compression factor is the inverse of the compression ratio.Source: §3.3 · pp. 4–5

4 COMPRESSION ALGORITHMS

The section surveys time-series compression algorithms across several approaches, then describes dictionary-based methods and their distinct mechanisms and constraints. These methods exploit shared segments, correlations, or repeated blocks, with trade-offs in accuracy, compression, dictionary size, and search cost.

4 COMPRESSION ALGORITHMS

  • The survey groups the algorithms into dictionary-based, function-approximation, autoencoder, sequential, and other approaches.The section summarizes each approach and provides pseudocode, prioritizing a homogeneous presentation over reproducing the original pseudocode exactly.Source: §4 · p. 5

4.1 Dictionary-Based (DB)

  • Dictionary-based compression represents shared time-series segments as dictionary atoms and replaces matching segments with their keys.Dictionary training balances reconstruction error against compression factor; unmatched segments may remain uncompressed or become new entries.Source: §4.1 · p. 6

4.1.1 TRISTAN.

  • TRISTAN learns or receives a dictionary and represents each segment with a sparse binary combination of dictionary atoms, but its optimization problems are NP-hard.The survey notes that approximate results are computed for the learning problem and matching pursuit approximates the compression problem.Source: §4.1.1 · pp. 6–7

4.1.2 CORAD.

  • CORAD extends TRISTAN with autocorrelation information, using dictionary atoms for uncorrelated segments and correlation-based representations for the others.It computes segment correlations within time windows and sorts segments by the absolute sum of their correlations.Source: §4.1.2 · pp. 7–8

4.1.3 Accelerometer LZSS (A-LZSS).

  • A-LZSS combines match searching with offline Huffman codes, encoding a value with variable-length bits or a match index and length.Larger blocks generally improve compression but require larger Huffman code tables; the described brute-force search has complexity O(2^Dn·2^Ln), which hashing can improve.Source: §4.1.3 · p. 8

4.1.4 Differential LZW (D-LZW).

  • D-LZW replaces dictionary-matched blocks with indices and adds unmatched blocks to the dictionary, ensuring lossless compression but potentially creating oversized dictionaries.The survey considers it suitable for particular streams, such as words or characters, or data with quantized block values; a simple dictionary search is O(n).Source: §4.1.4 · p. 8

4.2 Function Approximation (FA)

Function-approximation methods compress time series by representing segments with functions or transformed coefficients. Their approaches vary from threshold-controlled polynomial fits to wavelet and frequency transforms, with computational cost noted for the DCT.

4.2 Function Approximation (FA)

  • Function approximation segments a time series and fits each segment with a selected function family, producing lossy compression without requiring a training phase.The approach is independent of the data domain, and reconstruction error can be bounded by the selected approximation threshold.Source: §4.2 · p. 8

4.2.1 Piecewise Polynomial Approximation (PPA).

  • PPA fits fixed- or variable-length segments with polynomials, choosing the longest prefix that stays within a threshold error.A higher error threshold increases compression while reducing reconstruction accuracy; a higher maximum degree slows compression and reduces compression factor but improves accuracy.Source: §4.2.1 · p. 9

4.2.2 Chebyshev Polynomial Transform (CPT).

  • CPT represents a time series as a sequence of finite Chebyshev polynomials, following the polynomial-approximation principle with a different polynomial family.The survey identifies two types, T_n(x) and U_n(x).Source: §4.2.2 · p. 9

4.2.3 Discrete Wavelet Transform (DWT).

  • DWT transforms a time series using wavelet functions, which start and end at zero after oscillation.The survey describes an application and gives transformation and recovery formulas.Source: §4.2.3 · p. 9

4.2.4 Discrete Fourier Transform (DFT).

  • DFT transforms time-series values into frequency coefficients that can be compressed by discarding near-zero coefficients or retaining a fixed fraction.The Fast Fourier Transform can compute the transformation efficiently.Source: §4.2.4 · pp. 9–10

4.2.5 Discrete Cosine Transform (DCT).

  • DCT compression, like DFT compression, discards near-zero coefficients or coefficients beyond a chosen index, but its computation is expensive.The survey points to efficient implementations as an option.Source: §4.2.5 · p. 10

4.3 Autoencoders

The section surveys neural-network approaches that encode time series into compressed representations or predict symbols. It covers recurrent and convolutional autoencoders and DZip’s lossless prediction model.

4.3 Autoencoders

  • An autoencoder encodes an n-dimensional input as an m-dimensional code (m < n), then decodes the code to reconstruct the input.Its encoder and decoder are symmetric parts of the network.Source: §4.3 · p. 10

4.3.1 Recurrent Neural Network Autoencoder (RNNA).

  • RNNA passes time-series elements and hidden states through an encoder, then uses its last hidden state to initialize a decoder that reconstructs each element.The decoder passes each reconstructed element to its next state.Source: §4.3 · p. 10, §4.3.1 · p. 11

4.3.2 Recurrent Convolutional Autoencoder (RCA).

  • Adding convolutional layers to a recurrent autoencoder lets it extract local fluctuations from complex time-series inputs.The variation is proposed in.Source: §4.3.2 · p. 11

4.3.3 DZip.

  • DZip combines bootstrap and supporter models to predict the next symbol from a fixed vocabulary for lossless compression.The bootstrap model outputs a probability distribution over the vocabulary; the supporter model improves its estimate.Source: §4.3.3 · p. 12

4.4 Sequential algorithms

Sequential algorithms chain simple compression techniques, including Huffman, delta, run-length, and Fibonacci coding. The section describes how DRH, Sprintz, RLBE, and RAKE combine or adapt these building blocks.

4.4 Sequential algorithms

  • Huffman coding replaces symbols with dictionary-assigned binary codes, while delta encoding represents each time-series element relative to its predecessor and run-length encoding represents repeated values as value-count pairs.More frequent Huffman symbols receive shorter codes.Source: §4.4 · pp. 12–13

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

  • With Q = 1, DRH is lossless; increasing Q raises its compression factor while lowering reconstruction accuracy.DRH combines delta, run-length, and Huffman coding.Source: §4.4.1 · p. 13, §4.4 · p. 13

4.4.2 Sprintz.

  • Sprintz targets IoT constraints with prediction, bit packing, run-length encoding of correct forecasts, and Huffman entropy coding.Its stated requirements include small blocks, fast decompression, and lossless reconstruction.Source: §4.4.2 · pp. 13–14

4.4.3 Run-Length Binary Encoding (RLBE).

  • RLBE is a five-step lossless method that combines delta encoding, run-length encoding, and Fibonacci coding.It is designed for devices with low memory and computational resources.Source: §4.4.3 · p. 14

4.4.4 RAKE.

  • RAKE uses a probability-independent dictionary whose codewords have at most one set bit, then compresses by scanning the preprocessed bits with a shifting rake.Its two phases are preprocessing and compression.Source: §4.4.4 · pp. 14–15

4.5 Others

The section groups additional algorithms that do not fit the preceding categories, using extrema, segment merging, or a probabilistic model to compress time series.

4.5.1 Major Extrema Extractor (MEE).

  • MEE uses important extrema as a lossy representation that preserves properties such as minima and maxima for visualization but cannot reconstruct the original data.Maximum points are defined similarly to minimum points.Source: §4.5.1 · p. 15

4.5.2 Segment Merging (SM).

  • Segment Merging replaces consecutive elements or segments in regularly timestamped series with a value-and-error summary, subject to maximum-error and maximum-duration constraints.The compressed result also serves as the reconstruction, without additional decoder computations.Source: §4.5.2 · p. 16

4.5.3 Continuous Hidden Markov Chain (CHMC).

  • CHMC assumes data generation follows a probabilistic Markov model and reconstructs data lossily by following the identified chain’s probabilities.The model represents finite states and transition probabilities.Source: §4.5.3 · p. 16

4.6 Algorithms summary

The survey classifies the described algorithms using its taxonomy and presents the classification in both tabular and graphical form.

4.6 Algorithms summary

  • Table 2 summarizes the properties of the compression algorithms according to the taxonomy.The classification applies the taxonomy described in Sections 3.2 and 4.Source: §4.6 · p. 17
  • Figure 1 presents the same algorithm classification graphically using Venn diagrams.Source: §4.6 · p. 17
  • In the classification, ✓ means a property is true, – means it is not, and NA means it is not applicable.Min ρ and max ϵ denote the ability to set a minimum compression ratio or maximum reconstruction error, respectively.Source: §4.6 · p. 17

5 EXPERIMENTAL RESULTS

The section compares experimental findings reported in the original studies, spanning varied datasets and accuracy and compression measures. Its intergroup synthesis shows that each algorithm family has distinct data, error, and computational trade-offs.

5.1 Algorithms

  • CORAD’s best reported MSEs were 0.03 on BAFU, 0.11 on GSATM, and 0.04 on ACSF1; its best reported compression ratios were 0.04 on ACSF1, 0.07 on BAFU, and 0.06 on GSATM.TRISTAN accuracy depends on time-series segment redundancy and correlation. Its compression ratios were 0.5 for RTE and 0.05 for ICDM; higher sparsity values (larger dictionaries) allow better compression ratios.Source: §5.1.2 · p. 18, §5.1.1 · p. 18
  • A-LZSS reports its best compression ratio at lookahead distance 5 and dictionary-atom length 10; increasing lookahead or decreasing atom length penalizes the ratio.D-LZW’s experiments are limited to EGC and PPG signals, although the authors compare it with Bzip2 and Gzip.Source: §5.1.3 · p. 19, §5.1.4 · p. 19
  • PPA’s reconstruction error stays below its maximum-deviation threshold, while higher polynomial degree improves precision and yields the best reported compression ratios of 0.06 for REDD and 0.02 for Office.CPT and DWT lack reported experimental results here; the survey describes their compression–error trade-offs as parameter-dependent, with larger CPT blocks associated with better compression and higher decompression error.Source: §5.1.5 · p. 19, §5.1.6 · p. 21, §5.1.7 · p. 21
  • RNNA reports RMSE ranges of 0.02–0.07 for univariate and 0.02–0.05 for multivariate datasets, with no significant accuracy difference between them; RCA lowers traffic-flow RMSE from 10.37 to 8.17 with a convolutional layer.RCA’s original study focuses on next-value prediction and does not report a compression ratio; DZip outperforms RNNA, with compression ratio depending on vocabulary size and original series size.Source: §5.1.10 · pp. 21–22, §5.1.11 · p. 23, §5.1.12 · p. 23
  • DRH suits temperature, pressure, and light data with relatively long constant intervals, while Sprintz’s compared algorithms all achieve higher compression factors on 8-bit than on 16-bit data.Sprintz’s FIRE forecasting improves compression, especially with Huffman coding compared with Delta coding.Source: §5.1.13 · p. 23, §5.1.14 · p. 23
  • RLBE reports good compression ratios with 10% variability and low processing time; RAKE achieves higher compression factors on less-sparse datasets only when sparsity values are lower.RAKE’s suitability is specifically for sparse time series.Source: §5.1.15 · p. 23, §5.1.16 · p. 24
  • MEE’s authors provide no accuracy results and recommend a compression ratio no smaller than the percentage of non-extremal points; Segment Merging’s ratio–error relationship varies by dataset.For a given dataset, that relationship can be used to choose a ratio corresponding to a desired maximum compression error; CHMC’s assessment is qualitative and focuses on humanoid-robot motions.Source: §5.1.17 · p. 25, §5.1.18 · p. 25, §5.1.19 · p. 25

5.2 Intergroup comparison

  • Dictionary methods trade dictionary storage and training efficiency against dataset size and repetitiveness; functional methods suit regular, low-fluctuation data, while autoencoders depend on training quality and data regularity.Sequential methods depend on sparsity and regularity, need no training, and suit low-computational resources; autoencoders can lose prediction capacity on data with different seasonality or distribution than their training set.Source: §5.2.1 · p. 26, §5.2.2 · p. 26, §5.2.3 · p. 26

6 CONCLUSIONS

The survey classifies time-series compression methods and compares their reported accuracy and compression ratios to help identify techniques suited to particular contexts. It concludes that suitability depends on series characteristics, compression constraints, and intended use.

6 CONCLUSIONS

  • The survey presents a taxonomy and synoptic accuracy and compression-ratio results to inform technique selection for specific contexts.Suitability may depend on fixed compression-ratio or accuracy requirements and dataset characteristics.Source: §6 · p. 26
  • Time-series regularity, sparsity, fluctuations, and periodicity shape which compression techniques are suitable.Function-approximation methods directly handle irregular timestamps; other approaches assume fixed intervals and require transformations.Source: §6 · p. 26
  • Lossy methods struggle with highly non-regular fluctuations, while function approximation and lossy autoencoders can reconstruct general trends.The survey attributes flattening peaks to function approximation and autoencoders, and overly large dictionaries to dictionary-based methods.Source: §6 · p. 27
  • Dictionary-based methods suit highly periodic series, and lossy autoencoders also improve reconstruction accuracy on periodic inputs.Source: §6 · p. 27
  • Compression requirements include ratio, reconstruction accuracy, speed, and training-data availability; sequential algorithms can compress quickly on low-capacity hardware.Methods requiring a training phase are unsuitable when no training set is available.Source: §6 · p. 27
  • Compression purposes include analysis, classification, and visualization, with different method families supporting each use.Function approximation and lossy autoencoders can reduce noise and outliers for analysis; autoencoders also support classification, while MEE and SM support visualization.Source: §6 · p. 27

A ALGORITHMS

The algorithm listings illustrate dictionary, approximation, neural, and coding approaches through pseudocode fragments.

A ALGORITHMS

  • A-LZSS searches for the longest dictionary match and emits the match position and length when it meets minM.Source: A ALGORITHMS · p. 28
  • Dictionary-based compression builds a segment dictionary, while A-LZSS emits Huffman-coded symbols when a match is shorter than minM.Source: A ALGORITHMS · pp. 27–28
  • Polynomial compression approximates prefixes and emits a polynomial segment when its error is below epsilon.The listing defines rho as the maximum polynomial degree and epsilon as the error threshold.Source: A ALGORITHMS · pp. 28–29
  • The RNN compressor tests reconstructed-segment error and sends the encoded segment when that error is below epsilon.Source: A ALGORITHMS · p. 29
  • The Huffman procedure builds a tree by repeatedly combining the two lowest-frequency elements, then returns the resulting dictionary.Source: A ALGORITHMS · p. 30
  • The DRH listing encodes repeated deltas together with a counter, using quantized deltas when Q exceeds 1.Source: A ALGORITHMS · p. 30
Loading 2101.08784v2…