A perennial problem in data analysis is the increasing dataset sizes. This trend dictates the need not only for more efficient compression schemes, but also for analytic operations that work directly on the compressed data. Efficient compression schemes can be designed based on exploiting inherent patterns and structures in the data. Data periodicity is one such characteristic that can significantly boost compression.
Periodic behavior is omnipresent, many types of collected measurements exhibit periodic patterns, including weblog data [1, 2, 3], network measurements [4], environmental and natural processes [5, 6], medical and physiological measurements. The aforementioned are only a few of the numerous scientific and industrial fields that handle periodic data.
When data contain inherent structure, efficient compression can be performed with minimal loss in data quality. This is achievable by encoding the data using only few high-energy coefficients in a complete orthonormal basis representation, e.g., Fourier, Wavelets, Principal Component Analysis (PCA).
In the data-mining community, searching on time-series data under the Euclidean metric has been studied extensively, as e.g., described in [8]. However, such studies have typically considered compression using only the first Fourier or wavelets. The use of diverse sets of coefficients has been studied as described in [1].
The majority of data compression techniques for sequential data use the same set of low-energy coefficients whether using Fourier [7, 8], Wavelets [9, 10] or Chebyshev polynomials [11] as the orthogonal basis for representation and compression. Using the same set of orthogonal coefficients has several advantages: First, it is immediate to compare the respective coefficients. Second, space-partitioning indexing structures, such as R-trees, may be directly used on the compressed data. Third, there is no need to store also the indices of the basis functions that the stored coefficients correspond to. The disadvantage may be that both object reconstruction and distance estimation may be far from optimal for a given fixed compression ratio.
Side-information may also be recorded, such as the energy of the discarded coefficients, to better approximate the distance between compressed sequences by exploiting the Cauchy-Schwartz inequality [13].
In US 2009/0204574 A1 (see [25]), the distance estimation between one compressed and one uncompressed data vector is examined.