Lamia Djebour

Reza Akbarinia

Florent Masseglia

Variable-Size Segmentation for Time Series Representation

Keywords: Time Series, SAX, Representation, Segmentation, Similarity Search, Information Retrieval

Given the high data volumes in time series applications, or simply the need for fast response times, it is usually necessary to rely on alternative, shorter representations of time series, usually with information loss. This incurs approximate comparisons of time series where precision is a major issue. We propose a new representation approach called ASAX, coming with two techniques ASAX EN and ASAX SAE, for segmenting time series before their transformation into symbolic representations. Our solution can reduce significantly the error incurred by possible splittings at different steps of the representation calculation, by taking into account the entropy of the representations (ASAX EN) or the sum of absolute errors (ASAX SAE), particularly for datasets with unbalanced (non-uniform) distributions. This is particularly useful for time series similarity search, which is the core of many data analytics tasks. We provide theoretical guarantees on the lower bound of similarity measures, and our experiments illustrate that our approach can improve significantly the time series representation quality.

Introduction

Many applications in different domains generate time series data at an increasing rate. That continuous flow of emitted data may concern personal activities (e.g., through smart-meters or smart-plugs for electricity or water consumption) or professional activities (e.g., for monitoring heart activity or through the sensors installed on plants by farmers). This results in the production of large and complex data, usually in the form of time series that challenges knowledge discovery [START_REF] Kashino | Time-series active search for quick retrieval of audio and video[END_REF][START_REF] Shasha | Tuning time series queries in finance: Case studies and recommendations[END_REF][START_REF] Ye | Time series shapelets: a new primitive for data mining[END_REF][START_REF] Rakthanmanon | Searching and mining trillions of time series subsequences under dynamic time warping[END_REF][START_REF] Raza | Practical data prediction for real-world wireless sensor networks[END_REF][START_REF] Huijse | Computational intelligence challenges and applications on large-scale astronomical time series databases[END_REF][START_REF] Soldi | Long-term variability of AGN at hard X-rays[END_REF][START_REF] Palpanas | Data series management: The road to big sequence analytics[END_REF][START_REF] Linardi | ULISSE: ultra compact index for variable-length similarity search in data series[END_REF][START_REF] Linardi | VALMOD: A suite for easy and exact detection of variable length motifs in data series[END_REF]. Data mining techniques on such massive sets of time series have drawn a lot of interest since their application may lead to improvements in a large number of these activities, relying on fast and accurate similarity search in time series for performing tasks like, e.g., Classification, Clustering, and Motifs Discovery [START_REF] Rakthanmanon | Searching and mining trillions of time series subsequences under dynamic time warping[END_REF][START_REF] Linardi | Matrix profile X: VALMOD -scalable discovery of variable-length motifs in data series[END_REF][START_REF] Zoumpatianos | Data series management: Fulfilling the need for big sequence analytics[END_REF].

As a consequence of the high data volumes in such applications, similarity search can be slow on raw data. One of the issues that hinder the analysis of such data is the dimensionality. This is why time series approximation is often used as a means to allow fast similarity search. SAX (Symbolic Aggregate ApproXimation) [START_REF] Lin | A symbolic representation of time series, with implications for streaming algorithms[END_REF] is one of the most popular time series representations, allowing dimensionality reduction on the classic data mining tasks. SAX constructs symbolic representations by splitting the time domain into segments of equal size where the mean values of segments represent the time series intervals. This approximation technique is effective for time series having a uniform and balanced distribution over the time domain. However, we observe that, in the case of time series having high variation over given time intervals, this division into segments of fixed length is not efficient.

To illustrate the impact of a fixed length division of the series into segments, let us consider Figure 1. It shows a set D of time series, taken from ECGFiveDays dataset of UCR Archive [START_REF] Dau | Hexagon-ML: The ucr time series classification archive[END_REF]. In this dataset, the time series length is 136 and the data distribution in the time domain is unbalanced. We can notice that there is almost no variation from time point 1 to 45 and from 95 to the end. On the other hand, the remaining part, from time point 45 to 95, shows an important variation in the data values. Figure 1b shows the SAX division on D, with a fixed-size segmentation on the time series. In this example, the segment size is 10, leading to 13 segments in total. If we take any time series X from D and convert it into its SAX representation, the first 4 segments are always represented by the same symbol, all the values of these 4 segments being close to each other. Actually, there is no need to consider these 4 distinct segments. And the same applies to the last 3 segments. Meanwhile, for segments 5-10, all the values of each segment are represented by a single symbol while the data values present great variations, causing a significant loss of information on these segments. As one can observe, it is not necessary to split the parts that are constant or where the variation is low since they don't carry any relevant information and would therefore better form a single segment. It is more efficient to divide into several small segments the parts where variation is important in order to preserve potentially relevant information as shown in Figure 1a. The splitting of Figure 1a is the actual splitting obtained by our variable-size segmentation approach using our ASAX SAE technique (based on the representations's sum of absolute errors) with a segment budget limited to 13. It would be rather counter-intuitive to merge segments 1-5 and 10-13, while it is the opposite for Figure 1b. But, the time intervals where data values show important differences should be split to create more segments, e.g., between time point 50 and 90. By proposing such a customized splitting, we aim at improving the performance of information retrieval algorithms that will rely on our data representation. As illustrated by our experiments, the precision gain of ASAX SAE compared to SAX for kNN search is 38% over the dataset of Figure 1 (i.e., ECGFiveDays dataset).

Our main contribution is to provide an adaptive interval distribution, rather than an equal distribution in time. However, the number of possible segmentations of k segments with n can be very high. Furthermore, when searching for the best variable-size segmentation, a large number of computation may be repeated. Therefore, it is important to efficiently carry out the computations involved. We propose an new time series representation approach, called ASAX, that by smart selection of variable-size segments from the time domain allows to significantly reduce the information loss in the time series representation. To perform the variable-size segmentation in ASAX, we propose two different techniques ASAX EN and ASAX SAE. Briefly, we make the following contributions in this paper:

-We propose two new representation techniques, called ASAX EN (based on the entropy) and ASAX SAE (based on SAE the Sum of Absolute Errors), that allow obtaining a variable-size segmentation of time series with better precision in retrieval tasks thanks to the lower information loss. -We propose a lower bounding method that allows approximating the distance between the original time series based on their representations in ASAX. -We propose an efficient algorithm, called ASAX DP, for improving the execution time of our segmentation approach, by means of dynamic programming. -We implemented our solution and conducted empirical experiments using several real world datasets. The results illustrate that it can obtain significant performance gains in terms of precision for similarity search compared to SAX, particularly for datasets with non-uniform distributions. They suggest that the more the data distribution in the time domain is unbalanced (nonuniform), the greater is the precision gain of our approach. For example, for the ECGFiveDays dataset that has a non-uniform distribution in the time domain, the precision of ASAX SAE is 93% and 82% for ASAX EN compared to 55% for SAX. Furthermore, the results illustrate the effectiveness of our dynamic programming algorithm ASAX DP, e.g., up to ×40 faster than the basic algorithm over some datasets.

This article is an extension of [START_REF] Djebour | Variable size segmentation for efficient representation and querying of non-uniform time series datasets[END_REF], with at least 30% of added value. Particularly, in Section 5, we propose ASAX SAE, that is a variable-size segmentation algorithm based on SAE measurement. The execution time of ASAX SAE is lower than that of previously proposed ASAX EN, and its precision is often better. Furthermore, in Section 6, we propose a dynamic programming solution, called ASAX DP, which significantly improves the execution time of ASAX SAE. In addition, in Section 8, we report new experimental results done for evaluating the performance of ASAX SAE and ASAX DP.

The rest of the paper is organized as follows. In Section 2, we define the problem we address. We discuss the related work in Section 3. In Section 4, we propose ASAX EN for efficient segmentation of time seires, and in Section 5, we propose ASAX SAE. In Section, 6 we propose ASAX DP, the dynamic programming version of ASAX SAE. In Section 7 we present a formula for approximating the Euclidean distance of time series based on their representation given by ASAX EN or ASAX SAE. In Section 8, we present the experimental evaluation of our approaches, and we conclude in Section 9.

Problem Definition and Background

In this section, we first present the background about SAX representation, and then define the problem we address.

D Time series database X, Y , Q Time series n = |X| The length of time series X l
The segment size w

The number of PAA segments a

The cardinality (the alphabet size) X

The PAA representation of time series X X

The SAX representation of time series X k the k nearest neighbors Table 1: Some frequently used symbols A time series X is a sequence of values X = {x 1 , ..., x n }. We assume that every time series has a value at every timestamp t = 1, 2, ..., n. Thus, all time series in a database have the same length. The length of X is denoted by |X|.

SAX allows a time series T of length n to be reduced to a string of arbitrary length w. Table 1 lists the notations used in this paper.

SAX Representation

Given two time series X = {x 1 , ..., x n } and Y = {y 1 , ..., y n }, the Euclidean distance between X and Y is defined as [START_REF] Faloutsos | Fast subsequence matching in time-series databases[END_REF]: Fig. 2: A time series X is discretized by obtaining a PAA representation and then using predetermined break-points to map the PAA coefficients into SAX symbols. Here, the symbols are given in binary notation, where 00 is the first symbol, 01 is the second symbol, etc. The time series of Figure 2a in the representation of Figure 2c is [first, first, second, fourth] (which becomes [00, 00, 01, 11] in binary).

ED(X, Y ) = n i=1 (x i -y i ) 2
The Euclidean distance is one of the most popular similarity measurement methods used in time series analysis.

The Symbolic Aggregate ApproXimation (SAX) is based on the Piecewise Aggregate Approximation (PAA) [START_REF] Lin | A symbolic representation of time series, with implications for streaming algorithms[END_REF] which allows for dimensionality reduction while providing the important lower bounding property as we will show later. The idea of PAA is to have a fixed segment size, and minimize dimensionality by using the mean values on each segment. Example 1 gives an illustration of PAA.

Example 1. Figure 2b shows the PAA representation of X, the time series of Figure 2a. The representation is composed of w = |X|/l values, where l is the segment size. For each segment, the set of values is replaced with their mean represented in the figure with solid horizontal lines. The length of the final representation w is the number of segments (and, usually, w << |X|).

By transforming the original time series X and Y into PAA representations X = {x 1 , ..., x w } and Y = {y 1 , ..., y w }, the lower bounding approximation of the Euclidean distance for these two representations can be obtained by:

DR f (X, Y ) = n w w i=1 (x i -y i ) 2
The SAX representation takes as input the reduced time series obtained using PAA. It discretizes this representation into a predefined set of symbols, with a given cardinality, where a symbol is a binary number. Example 2 gives an illustration of the SAX representation.

Example 2. In Figure 2c, we have converted the time series X to SAX representation with size 4, and cardinality 4 using the PAA representation shown in Figure 2b. The discretization is achieved by considering a series of breakpoints running parallel to the x-axis represented in the figure with dashed horizontal lines. for each segment depending on the PAA coefficient an alphabet symbol is mapped to that segment based on the breakpoints interval it falls in. We denote SAX(X) = [00, 00, 01, 11].

The lower bounding approximation of the Euclidean distance for SAX representation X = {x 1 , ..., xw } and Ŷ = {ŷ 1 , ..., ŷw } of two time series X and Y is defined as:

M IN DIST f ( X, Ŷ ) = n w w i=1 (dist(x i , ŷi )) 2
where the function dist(x i , ŷi ) is the distance between two SAX symbols xi and xi . The lower bounding condition is formulated as:

M IN DIST f ( X, Ŷ ) ≤ ED(X, Y ) 2.

Similarity Queries

The problem of similarity queries is one of the main problems in time series analysis and mining. In information retrieval, finding the k nearest neighbors (k-NN) of a query is a fundamental problem. Let us define exact and approximate k nearest neighbors.

Definition 1. (Exact k nearest neighbors) Given a query time series Q and a set of time series D, let R = ExactkN N (Q, D) be the set of k nearest neighbors of Q from D. Let ED(X, Y ) be the Euclidean distance between two time series X and Y , then the set R is defined as follows:

(R ⊆ D) ∧ (|R| = k) ∧ (∀a ∈ R, ∀b ∈ (D -R), ED(a, Q) ≤ ED(b, Q))
Definition 2. (Approximate k nearest neighbors) Given a set of time series D, a query time series Q, and ϵ > 0. We say that

R = AppkN N (Q, D) is the approximate k nearest neighbors of Q from D, if ED(a, Q) ≤ (1+ϵ)ED(b, Q),
where a is the k th nearest neighbor from R and b is the true k th nearest neighbor.

Time Series Approximation

The SAX representation proceeds to an approximation by minimizing the dimensionality: the original time series are divided into segments of equal size. This representation does not depend on the time series values, but on their length. It allows SAX to perform the segmentation in O(n) where n is the time series length. However, for a given reduction in dimensionality, the modeling error may not be minimal since the model does not adapt to the information carried by the series. Our claim is that, by taking into account the information carried by time series for choosing the segments, we may obtain significant increase in the precision of kNN queries. This issue motivated us for proposing an adaptive representation aiming at minimizing the information loss.

Problem Statement

Our goal is to propose a variable-size segmentation of the time domain that minimizes the loss of information in the time series representation.

The problem we address is stated as follows. Given a database of time series D and a number w, divide the time domain into w segments of variable size such that the representation of the times series based on that segmentation lowers the error of similarity queries.

Related Work

Several techniques have been yet proposed to reduce the dimensionality of time series. Examples of such techniques that can significantly decrease the time and space required for similarity search are: singular value decomposition (SVD) [START_REF] Faloutsos | Fast subsequence matching in time-series databases[END_REF], the discrete Fourier transformation (DFT) [START_REF] Agrawal | Efficient similarity search in sequence databases[END_REF], discrete wavelets transformation (DWT) [START_REF] Chan | Efficient time series matching by wavelets[END_REF], piecewise aggregate approximation (PAA) [START_REF] Keogh | Dimensionality reduction for fast similarity search in large time series databases[END_REF], random sketches [START_REF] Cole | Fast window correlations over uncooperative time series[END_REF], Adaptive Piecewise Constant Approximation (APCA) [START_REF] Chakrabarti | Locally adaptive dimensionality reduction for indexing large time series databases[END_REF], and symbolic aggregate approXimation (SAX) [START_REF] Lin | Experiencing sax: A novel symbolic representation of time series[END_REF].

SAX [START_REF] Lin | Experiencing sax: A novel symbolic representation of time series[END_REF] is one of the most popular techniques for time series representation. It uses a symbolic representation that segments all time series into equi-length segments and symbolizes the mean value of each segment. Some extensions of SAX have been proposed for improving the similarity search performance via indexing [START_REF] Shieh | isax: Indexing and mining terabyte sized time series[END_REF][START_REF] Camerra | Beyond one billion time series: indexing and mining very large time series collections with i SAX2+[END_REF]. For example, iSAX [START_REF] Shieh | isax: Indexing and mining terabyte sized time series[END_REF] is an indexable version of SAX designed for indexing large collections of time series. iSAX 2.0 [START_REF] Camerra | Beyond one billion time series: indexing and mining very large time series collections with i SAX2+[END_REF] proposes a new mechanism and also algorithms for efficient bulk loading and node splitting policy, which is not supported by iSAX index. In [START_REF] Camerra | Beyond one billion time series: indexing and mining very large time series collections with i SAX2+[END_REF], two extensions of iSAX 2.0, namely iSAX 2.0 Clustered and iSAX2+, have been proposed. These extensions focus on the efficient handling of the raw time series data during the bulk loading process, by using a technique that uses main memory buffers to group and route similar time series together down the tree, performing the insertion in a lazy manner.

There have been SAX extensions designed to improve the representation of each segment, while using the SAX fixed-size segmentation, e.g., [START_REF] Lkhagva | New time series data representation esax for financial applications[END_REF][START_REF] Sun | An improvement of symbolic aggregate approximation distance measure for time series[END_REF][START_REF] Zhang | Entropy-based symbolic aggregate approximation representation method for time series[END_REF]. For example, SAX TD improves the representation of each segment by taking into account the trend of the time series. It uses the values at the starting and ending points of the segments to measure the trend. TFSA [START_REF] Yin | Symbolic representation based on trend features for knowledge discovery in long time series[END_REF] and SAX CP [START_REF] Yahyaoui | A novel trend based sax reduction technique for time series[END_REF] are other trend-based SAX representation methods. TFSA proposes a representation method for long time series based on the trend, and SAX CP considers abrupt change points while generating the symbols in order to capture time series' trends.

ABBA [START_REF] Elsworth | ABBA: adaptive brownian bridge-based symbolic aggregation of time series[END_REF] is a symbolic representation of time series based on an adaptive polygonal chain approximation of the time series into a sequence of tuples, followed by a mean-based clustering to obtain the symbolic representation. However, the authors of ABBA have not proposed an approximate function for comparing the time series in their representation form, and this prevents ABBA from being used for kNN search over the representations.

To increase the quality of time series approximation, our ASAX approach is based on variable-length segmentation. ASAX is complementary to the existing SAX extensions, e.g., indexing based techniques or those that use the trend for representing the segments. This makes our variable-size segmentation an advantageous alternative for segmenting the time domain in indexing solutions like iSAX.

Adaptive SAX based on Entropy

In this section, we propose ASAX EN, our first variable-size segmentation technique for the time series representation. To create a segmentation with minimum information loss, ASAX EN divides the time domain based on the representation entropy.

In the rest of this section, we first describe the notion of entropy for the time series representation. Then, we describe our algorithm for creating the variablesize segments based on this measurement.

Entropy

Entropy is a mathematical function which intuitively corresponds to the amount of information contained or delivered by a source of information. This source of information can be of various types. The more the source emits different information the higher is the entropy. If the source always sends the same information, the entropy is minimal. Formally, entropy is defined as follows.

Definition 3. Given a set X of elements, and each element x ∈ X having a probability P x of occurrence, the entropy H of the set X is defined as:

H(X) = -x∈X P x × log P x
In our context, we calculate the entropy on a set containing the different symbolic representations obtained from the transformation of the original time series of a dataset according to a given segmentation. The entropy computed on this set allows to measure the quantity of information contained in the time series representations. Let us illustrate this using an example.

Example 3. Consider the database D={x,y,z} in Figure 3 where x, y and z are time series with l =8. Let us create a representation having two segments (e.g., 0-4, and 4-8) obtained by dividing the time domain into two segments of the same size (the split is represented with the red dashed line). Then we compute the entropy of the representation of the set D. To generate the representation of the time series x, y and z, they are discretized by obtaining their PAA representation and then using predetermined break-points to map the PAA coefficients into the corresponding symbols like the SAX representation proceeds. We have converted the 3 time series into symbolic representations with size 2, and cardinality 4. Thus, the symbolic representations of x, y and z are x = [00, 10], ŷ = [00, 10] and ẑ = [00, 10], respectively. We notice that the 3 time series have the same symbolic representation, thus, the set X consists of only this unique symbolic representation with an occurrence equal to 3., i.e., X = {[00, 10]}. The entropy H(X) of X is computed as follows:

H(X) = -(P (x = [00, 10]) × log 2 P (x = [00, 10]))
where the probability for the word x is P (x = [00, 10]) = 3 3 = 1. Therefore, we have H(X) = -(1 log 1) = 0 meaning that in the representation X there is no information allowing to distinguish the three original time series from each other. This is explained by the fact that they have the same representation with a fixed-size segmentation. In the next subsection, we describe our algorithm to create variable-size segments based on entropy.

Variable-Size Segmentation Based on Entropy Measurement

Given a database of time series D, and a number w, our goal is to find the k variable size segments that minimize the loss of information in time series representations.

Intuitively, our algorithm works as follows. First it splits the time domain into two segments of equal size. Then, it performs w -2 iterations, and in each iteration it finds the segment s whose split makes the minimum loss in entropy, and it splits that segment. By doing this, in each iteration a new segment is added to the set of segments. This continues until having w segments.

Let us now describe ASAX EN in more details. The pseudo-code is shown in Algorithm 1. It first splits the time domain into two equal parts and creates two segments that are included to the set segments (Line 1). Then, it sets the current number of segments, denoted as k, to 2 (Line 2).

Afterwards, in a loop, until the number of segments is less than w the algorithm proceeds as follows. For each segment i (from 1 to k), i is divided into two equal parts, if its size is greater than minSize, which is the minimum possible size of a segment, and it's default value is 1. Then, a temporary set of segments tempSegments is created including the two new segments and all previously created segments except i (i.e., expect the one that has been divided). Then, for each time series ts in the database D, the algorithm generates the symbolic representation of ts (denoted as word) using the segments included in tempSegments with the given cardinality a (Line 12), and inserts it to a hash table (Line 13). Note that for all time series, ASAX EN uses the same cardinality to map the PAA coefficients into the corresponding symbols. After having inserted all the representations of the time series contained in D to the hash table, the entropy of the representations is calculated (Line 14). If the entropy is higher than the maximum entropy obtained until now, the algorithm sets i as the segment to be split, and keeps the entropy of the representation. This procedure continues by splitting one of the segments at each time, and computing the entropy. The algorithm selects the one whose entropy is the highest, and updates the set of the segments by removing the selected segment, and inserting its splits to the set segments (Lines 18-20). Then, the variable k, which shows the number of current segments, is incremented by one. The algorithm ends if the number of segments is equal to the required number, i.e., w.

Example 4. Let us consider the dataset D in Figure 3 which represents the initialization of the algorithm, i.e., the time domain is divided into two segments of the same size. The next step is to create the 3rd segment by splitting one of the two existing segments. Two different scenarios are possible.

Scenario 1 :

The first scenario is shown in Figure 4a where the left segment is divided into two equal parts. We generate the symbolic representation of the time series x, y, and z by using the 3 segments. Let's assume the cardinality is 4. Then, x = [00, 00, 10], ŷ = [00, 00, 10] and ẑ = [00, 00, 10] are the symbolic representation of x, y and z, respectively. Thus, the set X 1 consists of only one representation [00,00,10] with an occurrence of 3, i.e., X 1 = [00, 00, 10]. The entropy is then calculated as: H(X 1 ) = -(P (x = [00, 00, 10]) log P (x = [00, 00, 10])) where P (x = [00, 00, 10]) = 3 3 = 1 and we have H(X 1 ) = -(1 log 1) = 0.

P (x = [00, 01, 11]) = 2 3 . Then, H(X 2 ) = -( 1 3 log 1 3 + 2 3 log 2 3 ) = 0.918.
After having calculated the entropy for the two scenarios, we see that H(X 1 ) < H(X 2 ). We aim to maximize the entropy, therefore we choose the segmentation generated in Scenario 2 for this iteration of our algorithm. We continue the next iterations, until the number of segment reaches w. Let us now analyze the complexity of ASAX EN algorithm. Let |D| be the number of time series in the database, n the time series length, and w the desired number of segments. In the while loop, the algorithm performs w-2+1 iterations, and in each iteration it tries the division of each segment and computes the entropy of the segmentation. Thus, in total the number of entropy computations is O(w 2 ). For each entropy computation, the database should be scanned, and the representation of each time series created. This is done in O(|D| × n). Therefore, in total the time complexity of the algorithm is O(|D| × n × w 2 ).

Uniform Distribution of Symbols

SAX breakpoints divide the value domain into regions of different size where small regions are concentrated on the middle of the value domain and regions at extreme values are larger. This is illustrated by Figure 5, with three time series from our motivating example in Figure 1 with 6 segments. The breakpoints of SAX with 10 symbols are represented by horizontal lines, and, logically, they appear close to the center of the distribution. If we keep such distribution of symbols, then we would have two issues. First, the extreme values of the series like those above 2 or below -4 would be assigned the same symbol (their PAA value on the segment would fall in the same symbol). Second, the adaptive segmentation would consider that the slight variations around zero are more important than the ones at extreme values, ending in irrelevant splits that favor minor information gain. For this reason, we propose to calculate the breakpoints differently. In ASAX EN, the discretization is done based on breakpoints that produce uniform distributions of symbols. These breakpoints divide the value domain into regions of equal size. In the case of Figure 5 the 10 symbol regions will be evenly distributed in the range of data values.

Adaptive SAX based on SAE

In this section, we propose ASAX SAE, our second variable-size segmentation approach for time series representation. Here, to create a segmentation with minimum information loss on time series approximation, ASAX SAE divides the time domain by taking into account the sum of absolute errors (SAE) of the representation with a bottom-up strategy instead of a top-down strategy as used in the previous approach. Our experimental results have shown that this method is faster than ASAX EN, and its precision is often better.

In the rest of this section, we first describe the notion of sum of absolute errors (SAE) for the time series representation, and then, we describe the algorithm that creates the variable-size segments based on SAE measurement.

Sum of Absolute Errors (SAE)

SAE (Sum of Absolute Errors) calculates the sum of the absolute difference between the actual and the estimated values. Formally, SAE is defined as follows.

Definition 4. Given a vector X of n elements and a vector X being the estimated values generated from X, SAE of the estimation is given by:

SAE(X, X) = n i=1 |x i -xi |
In our context, we calculate the SAE on the PAA representation obtained from the transformation of the original time series of a dataset according to a given segmentation. The SAE computed on this representation allows to measure the approximation error on the time series by the PAA representation compared to the original time series. The lower the SAE, the closer is the PAA representation to the original data.

By transforming a time series X = {x 1 , ..., x n } into a PAA representation X = {x 1 , ..., x w }, X is reduced to the PAA representation composed of w segments. For each segment, the set of values is replaced with their mean. We can compute the SAE for each segment, that is in this case, the sum of the absolute differences between each value (original value) and its segment's mean (estimated value). In the following, we explain how to compute the SAE of a PAA representation for a given segmentation.

Let X be the PAA representation of X with w segments. The SAE of X for a particular segment is the sum of the absolute errors for the time series values in this segment. Formally, SAE of X for a segment s i is computed as:

SAE(s i , x i ) = U B(si) j=LB(si) |x j -x i |
where s i is the selected segment, LB(s i ) and U B(s i ) are the start and end time points of s i respectively.

In the next subsection, we describe our algorithm that creates variable-size segments thereby providing an accurate representation of time series based on the SAE measurement.

Variable-Size Segmentation Based on SAE Measurement

Given a database of time series D, and a number w, our goal is to find the w variable size segments that minimize the loss of information in time series representations by minimizing the approximation error of these representations.

Intuitively, our algorithm works as follows. Based on a starting segment size value size, it firstly splits the time domain into segments of length size. The default value of size is 2. Let k be the initial number of segments. The algorithm performs k -w iterations, and in each iteration it finds the two adjacent segments s i and s i+1 whose merging gives the minimum SAE (MSAE) on the representations, and merges them. By doing this, in each iteration the two selected segments are merged to form a single segment which replaces them in the set of segments, reducing the number of segments by one. This continues until having w segments.

Let us now describe our algorithm in more details. The pseudocode is shown in Algorithm 2. It first sets the current number of segments, denoted as k, to n size where n is the length of time series (Line 1). Then, it splits the time domain into k segments of length size that are included to the set segments (the set containing the current segmentation) (Line 2).

Afterwards, in a loop, until the number of segments is more than w the algorithm proceeds as follows. For each segment s i (i from 1 to k -1), s i is merged with segment s i+1 to form a single segment denoted as s (Line 7). Then, for each time series ts in the database D, the algorithm generates its PAA representation on segment s and calculates the corresponding SAE and adds the result of the computed SAE to sae (Line 10).

After having calculated the sum of the SAE for the PAA representation of all the time series contained in D, if the SAE is less than the MSAE (minimum SAE) obtained so far, the algorithm sets i as the segment to be merged with the next one, and keeps the SAE of the representation (Lines 12, 13). This procedure continues by trying the merging of every two adjacent segments of segments at each time, and computing the SAE. The algorithm selects the merging whose SAE is the lowest, and updates the set of the segments by removing the selected segments, and inserting its merging to segments (Lines 14-16). Then, the number of current segments (i.e., k) , is decremented by one (Line 17). The algorithm ends when k gets equal to the required number, i.e., w. Let us illustrate the principle of our algorithm using an example. For simplicity, we consider a dataset containing only a single time series.

Example 5. Let us apply our algorithm on the time series X in Figure 6 by taking the initial size of 2 for the starting segments. Notice that the PAA encoding is represented with black horizontal lines. The algorithm starts by dividing the time domain into 5 segments of size 2. The next step is to reduce the number of segments from 5 to 4. For this purpose, the algorithm tests the merging of every two adjacent segments of the 5 existing segments, in order to find the one that has the minimum SAE. Four different scenarios are possible: Scenario 1: The first scenario is shown in Figure 7a where s 1 and s 2 of the initial segmentation (shown in figure 6) are merged into one segment. We calculate the values's mean on the resulting segment (denoted S1 in figure 7a), and then compute the SAE of this approximation that is SAE 1 (X, X) = 0.55.

Scenario 2: This scenario is shown in Figure 7b in which s 2 and s 3 of the initial segmentation are merged. As for Scenario 1, we compute the mean of X on the current segment S 2 . Here, SAE 2 (X, X) = 2.3.

Scenario 3: This scenario is shown in Figure 7c, where we merge s 3 and s 4 . For this merging (S 3 ), SAE 3 (X, X) = 2.2.

Scenario 4:

The last scenario is shown in Figure 7d, where we merge s 4 and s 5 . For this segment S 4 , SAE 4 (X, X) = 0.65.

We have calculated the SAE for the 4 scenarios. Since we aim to minimize the SAE, we choose Scenario 1 that leads to the minimum SAE value (MSAE), that is M SAE = 0.55 (obtained by merging s 1 and s 2 ). After merging the segments s 1 and s 2 , the algorithm continues the next iterations, until the number of segment reaches w.

Let us now analyze the complexity of ASAX SAE algorithm. Let |D| be the number of time series in the database, n the time series length, and w the desired number of segments. The initial number of segments is n size , where size is the initial size of the segments. In the while loop, the algorithm performs n size -w +1 iterations, and in each iteration it tries the merging of each segment with its next segment, and computes the SAE of the segmentation. The maximum value for n size is n, i.e., with size = 1. Thus, the maximum number of SAE computations is O(n -w) 2 . For each SAE computation, the database should be scanned, and the error of each time series representation computed. This is done in O(|D|×n). Therefore, in total the time complexity of the algorithm is O((n -w) 2 × |D| × n).

ASAX SAE based on Dynamic Programming

The ASAX SAE algorithm, which we presented in the previous section, can reduce significantly the information loss in time series representations and is much more efficient than ASAX EN in terms of accuracy and calculation time, as illustrated by our experiments. However, its execution time may be high, particularly over large time series datasets as shown by our experiments (e.g., see Figure 12 in Section 8). In this section, we present an efficient version of ASAX SAE, called ASAX DP, for improving the execution time of our segmentation technique using dynamic programming. In ASAX DP, we use a data structure (matrix) to keep track of the result of the SAE computation for each iteration. In the matrix, if the value of a cell (i, j) is positive, then it corresponds to the SAE of merging all adjacent segments from segment s i to segment s j . In each iteration, after testing the merging of two adjacent segments, the computed SAE of the merging is kept in the matrix, in order to be used in the case where this merging needs to be evaluated again in the next steps. Let us describe ASAX DP algorithm in more details. Algorithm 3 presents the pseudocode of the improved approach. As for the ASAX SAE algorithm (described in the previous section), ASAX DP splits the time domain into k segments of length size to create the set segments (Lines 1, 2). A matrix of size k × k denoted as matrix is allocated and all its values are initialized to -1 (Line 3). Then, in a loop, until the number of segments is more than w the algorithm proceeds as follows. For each segment s i (i from 1 to k -1), the algorithm tests the merging of s i with segment s i+1 . For this, the algorithm computes the position in the matrix corresponding to the merging of these two segments by finding the row and column number (r, c) (Line 9). If it is the first time that these two segments merging is tested (i.e., if the SAE value in the corresponding cell in the matrix is equal to -1), then the algorithm has to compute the SAE for each time series ts in the database D on the segment s made from merging s i and s i+1 (Line 13). By summing up the SAE of PAA representation of all the time series contained in D, ASAX DP adds the result of the computed SAE to sae and stores this value in the matrix by replacing the existing value (-1) by the calculated SAE (Line 14). In the case where the merging of s i and s i+1 has already been tested (i.e., if the SAE value in the matrix is not -1), the algorithm simply has to get the SAE value from the matrix which is already computed and sets sae to this value (Line 16). After having obtained the SAE value, if it is less than the MSAE (minimum SAE) obtained so far, the algorithm sets i as the segment to be merged with the next one, and keeps the SAE of the representation ( Lines 18,[START_REF] Palpanas | Data series management: The road to big sequence analytics[END_REF]. This procedure continues by testing the merging of every two adjacent segments of segments at each time by making use of the matrix to avoid redundant SAE computations. The algorithm selects the merg-ing whose SAE is the lowest, and updates the set of the segments (Lines 20-22). The procedure continues until k reaches the required number of segments w. Bellow, we illustrate our algorithm using an example. Example 6. Let us apply ASAX DP on the time series X shown in Figure 6 by taking the initial size of 2 for the segments. Suppose the number of desired segments is w = 3. The algorithm starts by dividing the time domain into 5 segments of size 2 and initializes the matrix that will keep track of the SAE computation (Figure 8a). This matrix's row (and column) size is 5 which is the initial number of segments, each value corresponds to a possible merging of the initial segments (two segments or more). The value of cell (i, j) in the matrix corresponds to the SAE of merging of all adjacent segments from s i to s j . The final number of segments is w=3, thus the algorithm consists of 2 steps:

      s1 s2 s3 s4 s5 s1 -1 -1 -1 -1 s2 -1 -1 -1 s3 -1 -1 s4 -1 s5       (a) Matrix initialization       s1 s2 s3 s4 s5 s1 0.55 -1 -1 -1 s2 2.3 -1 -1 s3 2.2 -1 s4 0.65 s5       (b) After step 1       s1 s2 s3 s4 s5 s1 0.55 2.76 -1 -1 s2 2.3 -1 -1 s3 2.2 -1 s4 0.65 s5       (c) After step 2
Step 1 : Reduce the number of segments from 5 to 4. The algorithm tests the merging of every two adjacent segments of the 5 existing segments, 4 different scenarios are possible (presented previously in Example 6). Each of these 4 merging possibilities are tested, the corresponding SAE for each possible merging is computed, and the results are stored in the matrix. Figure 8b shows the content of the matrix after the update (the updated values are in red). The possible scenarios are underlined. For this step, we choose the segmentation generated in Scenario 1 shown in Figure 7a, resulting from merging s 1 and s 2 , since it provides the minimum SAE value (MSAE), that is M SAE = 0.55.

Step 2 : Reduce the number of segments from 4 to 3. In the previous step, the initial segments s 1 and s 2 have been merged into a single segment. Now, we have 4 segments as shown in Figure 7a. To reduce the 4 segments to 3, three merging scenarios are possible:

Scenario 1: The first scenario is shown in Figure 9a where the first segment S 1 of Figure 7a( the segment resulting from merging s 1 and s 2 ) and S 2 are merged, i.e s 1 ,s 2 and s 3 of the initial segmentation are merged into one segment. This merging is tested for the first time until now (matrix [START_REF] Agrawal | Efficient similarity search in sequence databases[END_REF][START_REF] Chakrabarti | Locally adaptive dimensionality reduction for indexing large time series databases[END_REF]=-1), then, we calculate the values's mean of X on the resulting segment, and then compute the SAE that is SAE 1 (X, X) = 2.76. The matrix cell that corresponds to this merging is updated (Figure 8c).

Scenario 2: This scenario is shown in Figure 9b in which s 3 and s 4 of the initial segmentation are merged. This merging has already been tested in the previous step (matrix [START_REF] Chakrabarti | Locally adaptive dimensionality reduction for indexing large time series databases[END_REF][START_REF] Chan | Efficient time series matching by wavelets[END_REF] ̸ =-1), the SAE value is retrieved from our matrix from the cell [START_REF] Chakrabarti | Locally adaptive dimensionality reduction for indexing large time series databases[END_REF][START_REF] Chan | Efficient time series matching by wavelets[END_REF]. Here, SAE 2 (X, X) = 2.2.

Scenario 3: The last scenario is shown in Figure 9c, where we merge s 4 and s 5 . The SAE for this merging has been already computed in step 1, that is SAE 3 (X, X) = 0.65.

We have now the SAE for the three scenarios. We choose the minimum SAE value, that is M SAE = 0.65 corresponding to the segmentation generated in Scenario 3, which is chosen for this iteration. After this step, we have 3 segments shown in Figure 9c. Since, the number of segment reaches w, the algorithm ends. (c) Scenario 3

Fig. 9: The three different scenarios of ASAX SAE segmentation with 3 segments. Scenario 9c is selected since it provides the minimum SAE.

Lower Bounding of the Similarity Measure

Having introduced the new representation of time series, we will now define a distance measure on it. SAX [START_REF] Lin | Experiencing sax: A novel symbolic representation of time series[END_REF] defines a distance measure on the representation of time series as described in Section 2.1. Given the representation of two time series, the M IN DIST f function allows obtaining a lower bounding approximation of the Euclidean distance between the original time series. By the following theorem, we propose a lower bounding approximation formula for the case of variable size segmentation in ASAX (whether it is done by ASAX EN or ASAX SAE).

Theorem 1. Let X and Y be two time series. Suppose that by using ASAX we create a variable size segmentation with w segments, such that the size of the i th segment is l i . Let X and Y be the PAA representation of variable size of X and Y in ASAX, DR v (X, Y ) gives a lower bounding approximation of the Euclidean distance between X and Y :

DR v (X, Y ) = w i=1 ((x i -y i ) 2 × l i )
Let X and Ŷ be the representations of X and Y in ASAX obtained by converting X and Y into symbolic representation. Then, M IN DIST v ( X, Ŷ ) gives a lower bounding approximation of the Euclidean distance between X and Y :

M IN DIST v ( X, Ŷ ) = w i=1 (dist(x i , ŷi ) 2 × l i )
Proof : To generate the ASAX representation of a time series, we need to first generate its PAA representation using the variable size segmentation (by taking the mean of the time series in each segment), and then we convert the PAA representation to ASAX by creating a symbol for each segment.

Our proof is done in two steps. In the first step, we show that the distance of X and Y in the PAA representation, denoted as DR v (X, Y ), is lower than or equal to their Euclidean distance. In the second step, we show that

M IN DIST v ( X, Ŷ ) ≤ DR v (X, Y ).
Step 1 : In the first step, we show that the DR v distance lower bounds the Euclidean distance, that is :

n i=1 (x i -y i ) 2 ≥ w j=1 ((x j -y j ) 2 × l j ) (1)
To prove the above inequality, it is sufficient to prove that the PAA distance of two time series in each segment is lower than or equal to their Euclidean distance in the segment. Without loss of generality, let us take the first segment S 1 , and suppose that its size is l 1 . Thus, we need to prove the following inequality:

l1 i=1 (x i -y i ) 2 ≥ l1 i=1 ((x i -y i ) 2 (2)
Let X and Y be the means of time series X and Y , respectively. We can rewrite the above inequality as:

l1 i=1 (x i -y i ) 2 ≥ (X -Y ) 2 × l 1 Or : l1 i=1 (x i -y i ) 2 ≥ √ l 1 (X -Y ) 2
By squaring both sides, we have:

l1 i=1 (x i -y i ) 2 ≥ l 1 (X -Y ) 2
For each point x i in X, x i = X -∆x i . The same applies to each point y in Y .

Then, we substitute the rearrangement:

l1 i=1 ((X -∆x i ) -(Y -∆y i )) 2 ≥ l 1 (X -Y ) 2
After rearranging terms in the left-hand side, we have:

l1 i=1 ((X -Y ) -(∆x i -∆y i )) 2 ≥ l 1 (X -Y ) 2
Then, we expand the inequality using the binomial theorem:

l1 i=1 ((X -Y ) 2 -2(X -Y )(∆x i -∆y i ) + (∆x i -∆y i ) 2 ) ≥ l 1 (X -Y ) 2
By using distributive law and summation properties, we have:

l 1 (X -Y ) 2 -2(X -Y ) l1 i=1 (∆x i -∆y i ) + l1 i=1 (∆x i -∆y i ) 2 ≥ l 1 (X -Y ) 2
We know that x i = X -∆x i , which means that ∆x i = X -x i , and the same applies for ∆y i . l1 i=1

(∆x i -∆y i ) = l1 i=1 ((X -x i ) -(Y -y i )) = ( l1 i=1 X - l1 i=1 x i ) -( l1 i=1 Y - l1 i=1 y i ) = (l 1 X - l1 i=1 x i ) -(l 1 Y - l1 i=1 y i ) = ( l1 i=1 x i - l1 i=1 x i ) -( l1 i=1 y i - l1 i=1 y i ) = 0 -0 = 0
We substitute 0 into l1 i=1 (∆x i -∆y i ) in the inequality:

l 1 (X -Y ) 2 -0 + l1 i=1 (∆x i -∆y i ) 2 ≥ l 1 (X -Y ) 2
Then by subtracting n(X -Y ) 2 from both sides, we have:

l1 i=1 (∆x i -∆y i ) 2 ≥ 0
This always holds true, so it completes the proof.

Step 2 : Following the same method as in Step 1, we will show here that M IN DIST v lower bounds the DR v distance, that is :

w j=1 ((x j -y j ) 2 × l j ) ≥ w i=j (dist(x j , ŷj ) 2 × l j )
To prove the above inequality, it is sufficient to prove that M IN DIST v in each segment lower bounds the DR v distance in the segment. Without loss of generality, let us take the first segment S 1 , and assume that its size is l 1 . Thus, it is sufficient to prove the following inequality:

1 i=1 ((x i -y i ) 2 ) × l 1 ≥ 1 i=1 (dist(x 1 , ŷ1 ) 2 × l 1 )
The above inequality can be written as: l 1 (X -Y ) 2 ≥ l 1 (dist( X, Ŷ )) 2 . There are two possible scenarios for the symbols representing X and Y .

Case 1 : the symbols representing X and Y are either the same, or consecutive from the alphabet a, i.e. |( X -Ŷ )| ≤ 1. In this case the MINDIST value is 0. Therefore, the inequality becomes :

l 1 (X -Y ) 2 ≥ 0
which always holds true.

Case 2 : the symbols representing X and Y are at least two alphabets apart, i.e. |( X -Ŷ )| > 1. Let us assume that X is at a higher region than Y , i.e. X > Ŷ , otherwise, in the case where X < Ŷ , it can be demonstrated in the same way. dist( X, Ŷ ) = β X-1 -β Ŷ By substituting into the inequality, we have:

l 1 (X -Y ) 2 ≥ l 1 (β X-1 -β Ŷ ) 2
By removing l 1 from both sides, we have:

|X -Y | ≥ |β X-1 -β Ŷ | Since X > Ŷ and |( X -Ŷ )| > 1,
we can drop the absolute value notation and rearrange the terms:

X -β X-1 ≥ Y -β Ŷ We know that : β X-1 ≤ X < β X and β Ŷ -1 ≤ Y < β Ŷ which implies that X -β X-1 ≥ 0 and Y -β Ŷ < 0.
Then, the inequality always holds true, and this completes the proof.

Experiments

In this section, we report the results of experimental studies on the proposed ASAX segmentation approaches, i.e. ASAX EN, ASAX SAE and ASAX DP.

Datasets and Experimental Settings

We compared the ASAX EN and ASAX SAE representations with the existing SAX representation on datasets selected for their particular (lack of) uniformity.

Notice that SAX and its extensions in the literature use a fixed-size segmentation of the time domain.

The approaches are implemented in Python programming language and Numba JIT compiler is used to optimize machine code at runtime1 . The experimental evaluation was conducted on a machine using Ubuntu 18.04.5 LTS operating system with 20 Gigabytes of main memory, and an Intel Xeon(R) 3,10 GHz processor with 4 cores.

We carried out our experiments on several real world datasets from the UCR Time Series Classification Archive [START_REF] Dau | Hexagon-ML: The ucr time series classification archive[END_REF]. Table 2 gives basic information about the datasets: name, type, length of the time series (number of values). Almost all selected datasets have non-uniform distributions over time domain (see Figure 10), else SyntheticControl that has a quasi uniform distribution.

For each approach, the length w of the approximate representations is reduced to 10% of the original time series length. For the variable-size segmentation algorithms, ASAX SAE is initialized by splitting the time domain into segments of length 2 and for ASAX EN we set the default cardinality value to 32.

Precision of k-Nearest Neighbor Search

In this part of experiments, we compare the quality of ASAX and SAX representations on different datasets described in Table 2 by measuring the precision of the approximate k-NN search for both of the two approaches. The precision reported for each dataset represents the average precision for a set of arbitrary random queries taken from this dataset. The search precision for each query Q from a dataset D is calculated as follows :

p = |AppkN N (Q, D) ∩ ExactkN N (Q, D)| k
where AppkNN(Q,D) and ExactkNN(Q,D) are the sets of approximate k nearest neighbors and exact k nearest neighbors of Q from D, respectively. App-kNN(Q,D) is obtained using DR f distance measure for SAX and DR v for the ASAX representation and the set ExactkNN(Q,D) contains the k-NN of Q using the euclidean distance ED. AppkNN(Q,D) and ExactkNN(Q,D) use a linear search that consists in computing the distance from the query point Q to every other point in D, keeping track of the "best so far" result. The precision results are reported in Figure 10 where each dataset is plotted with the precision obtained (as percentage) for all approaches. The plots show the shape of the different time series of each dataset and we can notice that the distribution of time series over the time domain varies from one dataset to another. There are some datasets for which the distribution is quite balanced, those which undergo some variations and others whose variation increases a lot. We have noticed that the more the distribution of the data is unbalanced the more the gain is important. Let us take for example the ECGFiveDays dataset presented in Figure 10a and SyntheticControl shown in Figure 10i. On the first one, we were able to achieve a precision of 93% for ASAX SAE, 82% for ASAX EN while it is 55% for SAX, which is a significant gain in precision. This higher precision for our approaches is due to the variable-size segmentation which creates segments in the parts that undergo a significant variation (from time point 45 to 95 in ECGFiveDays), allowing ASAX SAE and ASAX EN to perform a better distribution of the segments according to information gain by creating several segments in the parts that undergo a significant variation that produces more accurate times series representations leading to a better result for the approximate kNN search.

For SyntheticControl we can see that the precision of the approximate k-NN search is the same for the three approaches which is 32%. In this dataset, the shape of the time series is balanced over the time, and the segmentations obtained by ASAX SAE, ASAX EN and SAX are the same, resulting in equivalent precision.

From the results, we can observe that ASAX SAE approach performs better than ASAX EN for most datasets, especially for the datasets with high variation. Globally, the results suggest the effectiveness of our approaches and their advantage over traditional SAX when applied to time series, especially those with unbalanced distribution over the time domain. Using ECGFiveDays dataset, Figure 11 shows the precision gain of ASAX EN and ASAX SAE compared to SAX, for different number of segments w = [START_REF] Huijse | Computational intelligence challenges and applications on large-scale astronomical time series databases[END_REF][START_REF] Lin | A symbolic representation of time series, with implications for streaming algorithms[END_REF][START_REF] Yahyaoui | A novel trend based sax reduction technique for time series[END_REF]65]. The initial length of the time series in the dataset is around 130. The precision gain is computed by dividing the difference between the precision of ASAX EN (or ASAX SAE) and SAX, over the precision of SAX.

The results illustrate that ASAX SAE performs better than ASAX EN for all values of w. They also show that for small values of w the precision gain is higher. The reason is that in these cases the loss of information with SAX is much higher than our approaches. This suggests the interest of using our approaches for high dimentionality reduction.

Execution time of variable-size segmentation algorithms

This subsection presents the time cost of the variable-size segmentation for our proposed algorithms. Figure 12 reports the segmentation time of ASAX EN and ASAX SAE on the datasets of our experiments. It does not concern SAX since SAX divides the time domain into segments of fixed size which does not require any computation beforehand. The segmentation time depends on both the number of time series in the dataset and their length. We can observe that the time cost of ASAX SAE is always less than the one for ASAX EN.

Let us now compare the variable-size segmentation time cost of the improved algorithm ASAX DP with that of the basic algorithm ASAX SAE. Figure 13 reports the performance gains of ASAX DP compared to ASAX SAE, in logarithmic scale. The variable-size segmentation time for the two methods is evaluated for the same datasets used previously. We can observe that ASAX DP is much more efficient and allows to have significant performance gains.

Conclusion

We addressed the problem of approximating time series, and proposed ASAX EN and ASAX SAE, new techniques for segmenting time series before their transformation into symbolic representations. Our solutions can reduce significantly the error incurred by possible splittings at different steps of the representation calculation, by taking into account the sum of absolute errors (ASAX SAE) or the entropy (ASAX EN). We also proposed an efficient algorithm, called ASAX DP, for improving the execution time of our segmentation approach, by means of dynamic programming. We evaluated the performance of our segmentation approach through experiments using several real world datasets. The results suggest that the more the data distribution in the time domain is unbalanced (nonuniform), the greater is the precision gain of ASAX EN and ASAX SAE. For example, for the ECGFiveDays dataset that has a non-uniform distribution in the time domain, the precision of ASAX SAE is 93% and 82% for ASAX EN compared to 55% for SAX. Furthermore, the results illustrate the effectiveness of our dynamic programming algorithm ASAX DP, e.g., up to ×40 faster than the basic ASAX SAE algorithm over AllGestureWiimoteZ dataset.

Fig. 1 :

 1 Fig. 1: ASAX SAE segmentation vs. SAX segmentation

  A SAX representation of X, with 4 segments and cardinality 4, [00, 00, 01, 11]

Fig. 3 :

 3 Fig. 3: ASAX EN segmentation with 2 segments

Scenario 2 :

 2 This scenario is shown in Figure 4b in which the right segment is split. As for Scenario 1 we generate the symbolic representation of time series x, y and z using the 3 segments, and cardinality of 4. x = [00, 01, 10], ŷ = [00, 01, 11] and ẑ = [00, 01, 11] are the symbolic representation of x, y and z, respectively. In this scenario the representation set X 2 consists of [00,01,10] with an occurrence of 1 and [00,01,11] with an occurrence of 2, i.e., X = [00, 01, 10], [00, 01, 10]. The entropy is calculated as: H(X 2 ) = -(P (x = [00, 01, 10]) log P (x = [00, 01, 10]) + P (x = [00, 01, 11]) log P (x = [00, 01, 11])) where P (x = [00, 01, 10]) = 1 3 and Algorithm 1: ASAX EN variable-size segmentation Input: D: time series database; n: the length of time series; minSize: the minimum possible size of a segment; a: cardinality of symbols; w: the required number of segments Output: w variable-size segments segments = {[0, n 2 -1], [ n 2 , n -1]}; // split time domain into two equal size segments k = 2 while k ̸ = w do segmentT oSplit = 1 entropy = 0 for i=1 to k do tempSegments = segments if length(tempSegments[i]) > minSize then 9 split segment i into two equal parts, and replace the segment i by its corresponding parts in tempSegments 10 hashtable = new HashTable 11 foreach ts ∈ D do 12 word = Symbolic-Representation(ts, tempSegments, a) 13 hashT able.put(word) 14 e = entropy(hashT able) 15 if e > entropy then 16 segmentT oSplit = i 17 entropy = e split segmentT oSplit into two equal size segments s1 and s2 segments = segments -{segmentT oSplit} segments = segments {s1, s2} k = k+1 return segments

  Scenario 2 of ASAX EN segmentation with 3 segments

Fig. 4 :

 4 Fig. 4: The two different scenarios of ASAX EN segmentation with 3 segments. Scenario 4b is the one chosen because it optimizes the entropy.

Fig. 5 :

 5 Fig. 5: The Gaussian based distribution of symbols in SAX are not suitable for ASAX EN since they would favor minor information gain.

Fig. 6 :

 6 Fig. 6: The PAA representation of time series X contains 5 segments.

Fig. 7 :

 7 Fig. 7: The four different scenarios of ASAX SAE segmentation with 4 segments. Scenario 1 is the one chosen because it provides the minimum SAE.

Fig. 8 :

 8 Fig. 8: State of the matrix at different steps of the algorithm. The updated values are in red and the possible scenarios are underlined in each step.

Fig. 10 :Fig. 10 :

 1010 Fig. 10: The data distribution of the tested datasets, and the precision results for each dataset. p(SAX), p(ASAX EN) and p(ASAX SAE) show the precision of SAX, ASAX EN and ASAX SAE respectively.

Fig. 11 :

 11 Fig. 11: Precision gain of ASAX EN and ASAX SAE compared to SAX on the ECGFiveDays dataset, for different values of segments w =[10,13,26,65].

Figure 14 reportsFig. 12 :Fig. 13 :Fig. 14 :Fig. 15 :

 1412131415 Fig. 12: Logarithmic scale. Runtime of ASAX SAE and ASAX EN segmentation algorithms for each dataset

Table 2 :

 2 Datasets basic informationIn the experiments, we measure the precision of the compared approaches in similarity search, by applying a k-Nearest Neighbor (k-NN) search, as detailed in Subsection 8.2. For ASAX variable-size segmentation algorithms, we measure the time cost of the variable-size segmentation in Subsection 8.3.

k = k-1 18 return segments

Our code is available at : https://github.com/lamiad/ASAX

Algorithm 2: ASAX SAE variable-size segmentation

Input: D: time series database; n: the length of time series; size: the starting size of segments; w: the required number of segments Output: w variable-size segments