Esther Professora

Pacitti

Patrick Valduriez

Manoel E Luis

Felipe Souza

Keywords: Spatial-Time Series, Motifs, Restricted Sequences LIST OF ALGORITHMS Algorithm 3 -AAMP Algorithm Algorithm 4 -Combined Series Approach Algorithm 5 -CSTMP Algorithm 6 -BlockSearch

Discovering Motifs Restricted in Space-Time

Many phenomena can be observed and organized as a sequence of observations on a timeline that can be modeled as a time series. A relevant area that is being explored in time series analysis is pattern discovery. Patterns are subsequences of time series related to some special properties or behaviors. A particular pattern that occurs a significant number of times in time series is called motif. Several important phenomena of a time series present different behaviors when observed at points in space (for example, series collected by sensors and IoT) and are best modeled as space-time series. Each time series is associated with a position in space. A space-time pattern is a sequence of events that are limited in space and time. Finding patterns that are frequent and restricted in space and time can allow us to understand how a phenomenon occurs.

Several works have been developed to identify motifs in time series. However, studies that address spatiotemporal data techniques have not been identified. In this thesis, we compare different approaches to identifying motifs in time series with their main differences. We propose two methods for automatically identifying space-time restricted motifs in space-time series, the CSA and CST M P . We experimentally compare the proposed methods with two other alternative methods: the Matrix Profile technique and the ensemble of the Matrix Profile and DBScan techniques. Our results show that CSA and CST M P are innovative and obtain results that outperform the state-of-the-art techniques for time series and their adaptations for space-time series, being evaluated in two datasets.

LIST OF FIGURES

those that cover a greater number of spatial-time series.

LIST OF TABLES

1-Introduction

Under the data deluge scenario, data scientists are pushed to provide new ways for efficiently collecting, storing, processing, and organizing a large amount of data [START_REF] Tsai | Big data analytics: a survey[END_REF]. We are immersed in a scenario with massively growing datasets from many sources, types, and formats. The analysis of this data can reveal useful information and significant insights about the domain. Such scenario opens a set of research opportunities involving knowledge discovery [START_REF] Han | Data Mining: Concepts and Techniques[END_REF][START_REF] Shumway | Time Series Analysis and Its Applications: With R Examples[END_REF]. In this context, many phenomena can be observed and organized as a sequence of observations in a timeline that can be modeled as a time series, enabling discoveries.

A relevant area that is being explored in time series analysis is finding patterns [START_REF] Patel | Mining motifs in massive time series databases[END_REF]. Patterns are sub-sequences of time series that are related to some special properties or behaviors [START_REF] Han | Frequent pattern mining: Current status and future directions[END_REF]. Earlier efforts on frequent patterns discovery focused on finding association rules on transactional databases. In this context, a transaction is a set of items and we want to extract frequent subsets of items, also called itemsets, according to a given threshold. The problem of pattern mining successively evolved to augmented versions, according to data characteristics and analytics objectives, including sequential pattern mining where the temporal dimension of records is considered.

It concerns, for instance, successive transactions belonging to the same customer [START_REF] Han | Frequent pattern mining: Current status and future directions[END_REF].

The discovery of pattern enables the understanding of some specific behaviors observed in time series, in many areas of knowledge, such as weather prediction [START_REF] Mcgovern | Identifying predictive multi-dimensional time series motifs: An application to severe weather prediction[END_REF], wind generation [START_REF] Fan | Identifying and exploiting diurnal motifs in wind generation time series data[END_REF], image recognition [START_REF] Chi | Face image recognition based on time series motif discovery[END_REF],

seismic amplitude [START_REF] Cassisi | Motif Discovery on Seismic Amplitude Time Series: The Case Study of Mt Etna 2011 Eruptive Activity[END_REF]. A vast number of patterns discovery techniques, methods, and algorithms have been developed [START_REF] Mueen | Time series motif discovery: Dimensions and applications[END_REF][START_REF] Serr À | Particle swarm optimization for time series motif discovery[END_REF][START_REF] Torkamani | Survey on time series motif discovery[END_REF][START_REF] Yeh | Time series joins, motifs, discords and shapelets: a unifying view that exploits the matrix profile[END_REF]. They include discovering patterns of a particular/variable length [START_REF] Li | Approximate variable-length time series motif discovery using grammar inference[END_REF][START_REF] Tang | Discovering original motifs with different lengths from time series[END_REF], or without constraints (parameter-free algorithms) [START_REF] Nunthanid | Parameter-free motif discovery for time series data[END_REF], or in multivariate time series [START_REF] Minnen | Discovering multivariate motifs using subsequence density estimation and greedy mixture learning[END_REF]Yeh et al., 2017a].

However, various important time-series phenomena present different behaviors when observed at points of space (for example, series collected by sensors and IoT devices) and are better modeled as spatial-time series, in which each time series is associated to a position in space [START_REF] Fu | A review on time series data mining[END_REF]. This scenario motivates the definition of new techniques for pattern mining, dedicated to spatio-temporal datasets [START_REF] Fu | A review on time series data mining[END_REF][START_REF] Mooney | Sequential pattern mining -Approaches and algorithms[END_REF]. Under such scenarios, some patterns might not be discovered when we restrict the analysis to the time-only dimension. The challenge becomes to identify regions of space and time where the patterns are frequently observed. Finding patterns that are frequent in a constrained space and time, i.e., finding spatial-time patterns, may enable us to comprehend how a phenomenon occurs.

Consider as an example the spatial-time series dataset at the seismic surveys. In some applications, there is a need for analyzing the subsoil structure of a large terrain area to discover specific interesting information like specific boundaries between geologic layers [START_REF] Zhou | Practical Seismic Data Analysis[END_REF]. For that purpose, a set of receivers are placed in specific fixed positions of a large terrain area and each of them captures the values reflected by the different materials of the subsoil. In this way, each receiver indicates the position of a time series where the time is related to the subsoil depth in a form that the earlier values are more superficial.

This operation collects a huge volume of three-dimensional spatial-time data that needs to be analyzed to find specific interesting patterns. In this domain, finding a frequent pattern of textures in the entire dataset is of little interest. However, some patterns (Figure 1) occurring in a constrained depth interval and a specific space location may lead to highly valuable lithology change indicator such as horizons, indicated by the numbers 1, 3 and 4

(which stand for kind of layers) or bright spots, indicated by the number 2 (potential areas of hydrocarbon accumulation) [START_REF] Zhou | Practical Seismic Data Analysis[END_REF].

Spatial -Crossline

Time (z-range) This work addresses such problem by presenting approaches to discover patterns that are frequent on a constrained time and space and may not be frequent in the entire dataset. Defining the input data as a collection of spatio-temporal series, where each time series is a collection of observations and each observation is a continuous (non-discrete) value, we aim to find all patterns that are frequent in a constrained space and time. To tackle this problem, we propose in this work two evolving approaches.

At first, we propose an approach to discover and rank motifs in spatial-time series, denominated Combined Series Approach (CSA). CSA is based on partitioning the spatial-time series into blocks, combining subsequences of spatial-time series. Motifs are validated according to both temporal and spatial constraints and ranked according to their entropy, the number of occurrences, and the proximity of their occurrences.

At the second approach, we introduce the Constrained Spatio-Temporal Matrix

Profile (CST M P ) algorithm. CST M P it is an adaptation of the Matrix Profile approach [START_REF] Yeh | Matrix profile I: All pairs similarity joins for time series: A unifying view that includes motifs, discords and shapelets[END_REF] in order to discover motifs that are restricted in space-time in spatiotemporal data that span two spatial dimensions. In CST M P , the distance between the neighboring space-time series' sub-sequences is calculated iteratively by identifying and grouping the motifs that are directly reachable by density with each other.

We evaluated our approaches on a synthetic and on the seismic dataset. They were able to identify spatial-time patterns that could not be identified using the traditional approach. Besides, they were able to prioritize patterns that were meaningful according to their number of occurrences and quality. Our approaches outperform traditional methods designed only for time series, managing to find sets of motifs with different configurations as demonstrated in the synthetic dataset experiments. Moreover, the identified patterns on the seismic dataset correspond to candidate areas for seismic horizons and bright spots that are of high value for domain experts.

In addition to this introduction, this work is organized as follows. Chapter 2 presents the background for time series data mining and the Related Works from Motif Discovery, including the main concepts, evidencing the differences with the solution proposed in this work. Chapter 3 formalizes the problem definition. Chapter 4 presents the CSA, our first approach to discovery spatial-time motifs. In Chapter 5 we deeper our analysis and present CST M P , which is an evolved approach based on Matrix Profile. Chapter 6 describes and explains the experiments using CSA and the CST M P . Finally, chapter 7

presents the conclusion and future work.

2-State of the art

In this chapter, we introduce the general concepts about time series, spatial-time series, sub-sequences, sliding windows, normalization, and data indexing. Concepts related to motif discovery. In addition, state of the art motif discovery techniques are explored.

2.1-Background

A time series t is an ordered sequence of values in time:

t =< t 1 , t 2 , • • • , t m > , t i 2 R,
where each t i is a value, |t| = m is the number of elements in t, and t m is the most recent value in t [START_REF] Shumway | Time Series Analysis and Its Applications: With R Examples[END_REF].

A subsequence is a continuous sample of a time series with a defined length.

The p th subsequence of size n in a time series t, represented as seq n,p (t), is an ordered sequence of values < t p , t p+1 , . . ., t p+n 1 >, where |seq n,p (t)| = n and 1  p  |t| n.

Subsequences enable the analysis of data samples to evaluate some local properties [START_REF] Chiu | Probabilistic discovery of time series motifs[END_REF].

Sliding windows consist in exploring all possible subsequences of a time series [START_REF] Keogh | Clustering of time-series subsequences is meaningless: Implications for previous and future research[END_REF][START_REF] Lampert | Beyond sliding windows: Object localization by efficient subwindow search[END_REF]. Sliding windows produce a set of subsequences of the same length. A sliding windows of size n for a time series t is a function

sw n (t) that produces a matrix W of size (|t| n + 1) by n. Each line w i in W is the i-th subsequence of size n from t. Given W = sw n (t), 8w i 2 W , w i = seq n,i (t).
This concept is widely used in time series analysis to make comparisons between subsequences to find their similarities [START_REF] Van Hoan | Time series symbolization and search for frequent patterns[END_REF]. A spatial-time series st can be described as a pair (t, p), such as a time series t et al., 2020] with an associated position p [START_REF] Shekhar | Spatial computing[END_REF]. The position can be its geographical coordinates or any other reference that can represent the place where data has been observed. If the position is a function of time, it is a trajectory spatial-time series. Otherwise, it is a permanent spatial-time series. In this work, we are interested in permanent spatialtime series and for the sake of simplicity, from now on, we are calling them spatial-time series.

Data preprocessing techniques are key activities for enabling or improving the quality of data mining. In time series context, data is usually a continuous numerical value.

For pattern discovery, some methods do not process them efficiently [START_REF] Daw | A review of symbolic analysis of experimental data[END_REF].

Due to that, during pattern discovery, two data preprocessing techniques are commonly applied in sequence: (i) data normalization and (ii) Symbolic Aggregate Approximation (SAX).

Normalization is commonly used to enable the effectiveness of time series comparison methods. One of the most common normalization methods is z-score [START_REF] Keogh | Exact indexing of dynamic time warping[END_REF]. As a result of this normalization method, the normalized time series has zero as average and one as standard deviation. Equation 1 (a) describes z-score normalization, where t i is an observation of the time series t, µ t is the average, t is the standard deviation of the time series, and t 0 is the transformed time series. Additionally, the min-max is another normalization method that applies a linear transformation to the original data, where the minimum value (min(t)) and the maximum value (max(t)) are used to transform each value t i to another value t 0 i in a range varying from [0, 1], as shown in Equation 1(b) [START_REF] Ogasawara | Neural networks cartridges for data mining on time series[END_REF].

t 0 i = (t i µt) t t 0 i = t i min(t) max(t) min(t) (a) ( b) (1)
SAX is an indexing technique. It consists primarily in partitioning the domain of a variable into ranges such that each range is associated with a particular symbol [START_REF] Lin | Experiencing SAX: A novel symbolic representation of time series[END_REF]. The SAX alphabet size defines the number of partitions for the domain. Thus, all values are replaced by their respective associated symbol. Given an alphabet (a

1 , • • • , a n ) of size n, the values of time series t are divided into n ranges ([ 1, 1 ], • • • , [ n 1 , 1])
according to Gaussian function (with different sizes, but same probability), such that each value t i is mapped to an alphabet value a k , where 1  k  n [START_REF] Lin | A symbolic representation of time series, with implications for streaming algorithms[END_REF].

2.2-Motif discovery

Given a sequence q and time series t, q is a motif in t with support , if and only if q is included in t at least times. The length of a motif q (|q|) is also known as word size. Formally, given a sequence q and a time series t where W = sw |q| (t), motif (q, t, ) $ 9 R ✓ W , (|R| ), such that 8w i 2 R, w i = q [START_REF] Mueen | Time series motif discovery: Dimensions and applications[END_REF]. An important property regarding motifs is that the repeated subsequence is not previously known and is discovered when scanning the entire data. It can be discovered by making a comparison between subsequences that are obtained using sliding windows [START_REF] Chiu | Probabilistic discovery of time series motifs[END_REF].

Many methods proposed in the literature to discover motifs in time series are computationally intensive [START_REF] Patel | Mining motifs in massive time series databases[END_REF]. Due to that, many works aim to improve the effectiveness of motif discovery and reduce the computational resources needed. Such a process requires some data preprocessing such as normalization and indexing before running the motif discovery algorithms to increase the performance and precision of results [START_REF] Mueen | Time series motif discovery: Dimensions and applications[END_REF].

There are some main approaches to discover motifs, such as (i) brute force; (ii) heuristic-based; and (iii) matrix profile. The brute force approach is the simplest method. It has a high computational cost, especially when used to discover sequences of greater size in large datasets [START_REF] Mueen | Exact discovery of time series motifs[END_REF]. It is indicated for discovering sequences of smaller size [START_REF] Li | Probabilistic discovery of motifs in water level[END_REF]. In this method, the coverage and accuracy are complete since it makes all possible comparisons between all subsequences of a time series. For the sake of our work, we can group time series motif discovery approaches according to the exactness (exact or approximate), length (fixed or variable), and dimension (single or multiple).

The brute force approach is the simplest method, but it has a high computational cost, specially when used for large dataset [START_REF] Mueen | Exact discovery of time series motifs[END_REF]. It is indicated for low dimensional data [START_REF] Li | Probabilistic discovery of motifs in water level[END_REF]. In this method the coverage and accuracy is complete since it makes all possible comparisons between all subsequences of a time series.

The random projections approach was proposed to handle large dataset reducing dimensionality taking samples of data aleatory [START_REF] Li | Probabilistic discovery of motifs in water level[END_REF]. It optimizes the execution time and reduces the computational consumption in identifying motifs [START_REF] Buhler | Finding motifs using random projections[END_REF][START_REF] Chiu | Probabilistic discovery of time series motifs[END_REF]. In random projection, the search for similar subsequences is speed-up using hash-based methods for matching certain random elements of the sequence. It includes SAX indexing and sliding windows. Each symbolic subsequence is inserted in a subsequences matrix. Each line index corresponds to the initial position of subsequence in time axis. The next step is to build the collision matrix which is used to indicated potential motifs in the time series. The collision matrix is initially null and has the same quantity of lines and columns that correspond to the total number of subsequences identified. The collision matrix is built from the random projection process where two columns of the subsequence matrix are randomly selected and mask and for each position in mapped as a hash structure that has as input the symbolic values that correspond to position of selected columns. If two subsequences has the same symbolic value in the mask position then it is placed in hash structure.

The matrix profile is based on computing the distance of a sequence of size n with the most similar subsequence present in the time series. It is called matrix profile, since the naive implementation of this technique is to compute all pairwise distance for all sequences present in the time series. However, it can use efficient algorithms, such as Fast Fourier Transform (FFT) to enable very fast computation [START_REF] Yeh | Time series joins, motifs, discords and shapelets: a unifying view that exploits the matrix profile[END_REF]. Matrix profile has two manifold advantages. It can handle numeric data directly and uses a matrix for support comparisons of subsequences which can be used to other tasks rather than motif discovery [START_REF] Yeh | Matrix profile I: All pairs similarity joins for time series: A unifying view that includes motifs, discords and shapelets[END_REF][START_REF] Yeh | Time series joins, motifs, discords and shapelets: a unifying view that exploits the matrix profile[END_REF][START_REF] De Paepe | A generalized matrix profile framework with support for contextual series analysis[END_REF]. Due to its important, a entire section is dedicated to it. The default distance measure used is the z-normalized Euclidean distance, which removes the effect of a changing data offset over time and thus focuses more on shape instead of amplitude. Typical causes of a changing offset are wandering baselines in sensors or natural phenomena (e.g., the gradual change in temperature throughout seasons) [START_REF] De Paepe | A generalized matrix profile framework with support for contextual series analysis[END_REF].

2.3-Matrix Profile

We present three important algorithms for calculating the Matrix Profile, which are described in Sections 2.3.1, 5.1.1, and 2.3.3.

STAMP

The Matrix Profile was originally published together with the STAMP (Scalable Time Series Anytime Matrix Profile) [START_REF] Yeh | Matrix profile I: All pairs similarity joins for time series: A unifying view that includes motifs, discords and shapelets[END_REF], an anytime algorithm to calculate the Matrix Profile over a time series and the corresponding Index. Internally, STAMP uses a similarity search algorithm called MASS [START_REF] Mueen | The Fastest Similarity Search Algorithm for Time Series Subsequences under Euclidean Distance[END_REF] that under z-normalized

Euclidean iteratively calculates the distance of each subsequence to every subsequence by using the Fast Fourier Transform (FFT).

The STAMP is outlined in Algorithm 1. In line 2, the length of T B is extracted. In line 3, the matrix profile P AB and matrix profile index I AB are initialized. From lines 4

to line 6, the distance profiles D are calculated, using each subsequence B[idx] in the time series T B and T A . The pairwise minimum for each element in D is performed with the paired element in P AB (i.e., min(D[i], P AB [i]) for i = 0 to length(D) -1). Then, as the minimum pair operations are performed,

I AB [i] is updated with idx (when D[i]  P AB [i]).

STOMP

STOMP is similar to STAMP [START_REF] Keogh | On the Need for Time Series Data Mining Benchmarks: A Survey and Empirical Demonstration[END_REF] in that it can be seen as highly optimized nested loop searches, with the repeated calculation of distance profiles as the inner loop. However, while STAMP must evaluate the distance profiles in random order (to allow its anytime behavior), STOMP performs an ordered search. It is by exploiting the locality of these searches that STOMP can reduce the time complexity by a factor of O(n log n). STOMP uses the z-normalized Euclidean distance d i,j , as shown below, of two time series subsequences T i,m and T j,m using their dot product, QT i,j :

d i,j = s 2m ✓ 1 QT i,j mµ i µ j m i j ◆ (2)
Here m is the subsequence length, µ i is the mean of T i,m , µ j is the mean of T ( j, m), i is the standard deviation of T i,m , and j is the standard deviation of T j,m . Note that QT i,j can be decomposed as:

QT i,j = m 1 X k=0 T i+k T j+k (3)
The time required to compute d i,j depends only on the time required to compute QT i,j . To solve this problem, STOMP pre-computes and stores the means and standard deviation in O(n) space and time, thus, it takes O(1) to compute d i,j [START_REF] Yeh | Matrix profile I: All pairs similarity joins for time series: A unifying view that includes motifs, discords and shapelets[END_REF].

The pseudo-code of STOMP algorithm is shown in Algorithm 2. It begins in line 2 by computing the matrix profile length l. In line 3, it calculates the mean and standard deviation of every subsequence in T . Line 4 calculates the first dot product vector QT .

Line 5 initializes the matrix profile P and matrix profile index I. The loop in lines 6-13 calculates the distance profile of every subsequence of T in sequential order, with lines 7-9

updating QT according to (3). Then update QT [1] in line 10 is done with the pre-computed QT f irst in line 3. Line 11 calculates distance profile D according to (2). Finally, line 12 compares every element of P with

D: if D[j] < P [j], then P [j] = D[j], I[j] = i.
The time complexity of STOMP is O(n 2 ). Thus, it can achieve a O(n log n) factor speedup over STAMP [START_REF] Keogh | On the Need for Time Series Data Mining Benchmarks: A Survey and Empirical Demonstration[END_REF]. The O(n log n) speedup clearly makes little difference for small datasets, however, when considering the datasets with millions of data points, this O(n log n) factor begins to produce a significant performance gain.

QT [j] QT [j 1] T [j 1] ⇥ T [i 1] + T [j + m 1] ⇥ T [i + m 1] 10 QT [1] QT first [i] 11 D CalculateDistanceProfile (QT,

AAMP

In many applications it is preferred to not normalize the time-series data because the anomalies can be detected based on the point values, and not the shapes. AAMP [START_REF] Akbarinia | Efficient Matrix Profile Computation Using Different Distance Functions[END_REF] has been designed for such applications. It is an efficient algorithm for computing matrix profile with the pure (non-normalized) Euclidean distance.

AAMP is executed in a set of iterations, such that in each iteration the distance of subsequences is computed incrementally. The time complexity of AAMP is O(n ⇥ (n m))

with small constants, where n is the time series length and m the subsequence length.

The experiments reported in [START_REF] Akbarinia | Efficient Matrix Profile Computation Using Different Distance Functions[END_REF] show that the performance of AAMP is significantly better than that of STAMP and SCRIMP++ (an improved version of STOMP).

D i,j = q D 2 i 1,j 1 (t i 1 t j 1 ) 2 + (t i+m 1 t j+m 1 ) 2 (4)
The main idea behind AAMP is that for computing the distance between subsequences it uses diagonal sliding windows, such that in each sliding window, the Euclidean distance is incrementally computed only between the subsequences that have a precise difference in their start position. Let T i = ht i , t i+1 , . . . , t i+m 1 i and T j = ht j , t j+1 , . . . , t j+m 1 i be two subsequences. The sliding windows in AAMP allow to use Equation ( 4) for incre-mental computation of the distance between subsequences T i and T j (denoted by D i,j ) by using the yet computed distance between subsequences T i 1 and T j 1 (denoted as

D i 1,j 1 ).
Algorithm 3 -AAMP Algorithm Input: T : time series; n: length of time series; m: subsequence length Output: P : Matrix profile; 1 begin 2 for i=1 to n do 3

P[i] = 1 ; 4 for k=1 to n-m-1 do 5 dist = EucDistance(T 1,m , T k,m ) if dist ¡ P[1] then 6 P[1] = dist; 7 if dist ¡ P[k] then 8 P[k] = dist; 9 for i=2 to n -m + 1 -k do 10 dist = p (dist 2 (t i 1 t i 1+k ) 2 + (t i+m 1 t i+m+k 1 ) 2 if dist ¡ P[i] then 11 P[i] = dist; 12 if dist ¡ P[i+k] then 13 P[i+k] = dist;
Algorithm 3 shows the pseudo-code of AAMP. Initially, the algorithm sets all values of the matrix profile to infinity (i.e., maximum distance). Then, it performs n m 1 iterations using a variable k (1  k  n m 1). In each iteration k, the algorithm compares each subsequence T i,m with the subsequence that is k positions far from it, i.e., T i,m+k . To do this, AAMP firstly computes the Euclidean distance of the first subsequence of the time series, i.e., T 1,m , with the one that stars at position k, i.e., T k,m . This first distance computation is done using the normal formula of Euclidean distance. Then, in a sliding window, the algorithm incrementally computes the distance of other subsequences with the subsequences that are k position far from them, and this is done by using Equation (4) in O(1). If the computed distance is smaller than the previous minimum distance that is kept in the matrix profile P , then the smaller distance is saved in the matrix profile.

2.4-Related work

After motif discovering process, an important task in motif analysis is how to sort the motifs according to their relevance [START_REF] Castro | Significant motifs in time series[END_REF]. A standard classification method is k-motif which considers the total number of occurrences of the motifs in time series. Also, motifs can be sorted according to their relevance degree. For instance, some motifs can be similar to a straight line (i.e., constant observations) and depending on the data domain may not be relevant. Such motifs can be low qualified or discarded to avoid distorting the analysis [START_REF] Chiu | Probabilistic discovery of time series motifs[END_REF].

Some approaches to evaluate the significance and relevance of motifs were proposed in the literature. A statistical approach to assess the relevance of motifs is based on information gain which measures how expected is the motif to occurs [START_REF] Castro | Significant motifs in time series[END_REF]. The Log-odds considers the degree of how rare the motif is by comparing the amount of occurrence with the expected chance of having occurrence based on probabilistic distribution [START_REF] Yang | Mining surprising periodic patterns[END_REF]. [START_REF] Castro | Significant motifs in time series[END_REF] proposed the estimation of expectation for the frequency of a motif based on Markov Chain models. The value is assessed making the comparison between actual frequency and estimated based on hypothesis tests.

Considering the exact motif discovery approach, some specific method to address the dimensionality and motif length problem were proposed. [START_REF] Jiang | Finding motifs of financial data streams in real time[END_REF] proposed an efficient motif discovery algorithm PMDGS (P-Motif Discovery based on Grid Structure) that processes data streams. [START_REF] Mueen | Exact discovery of time series motifs[END_REF] proposed a motif discovery algorithm for exact time series called MK (Mueen-Keogh) and observed that MK was faster than brute-force [START_REF] Chiu | Probabilistic discovery of time series motifs[END_REF]. [START_REF] Narang | Parallel exact time series motif discovery[END_REF] When it comes to approximate motif discovery, the approaches aim to reduce the complexity and consequently the computational cost. Some work proposed approaches to improve the accuracy and efficiency of Random Projection Algorithm as proposed in [START_REF] Chiu | Probabilistic discovery of time series motifs[END_REF]. [START_REF] Lin | Experiencing SAX: A novel symbolic representation of time series[END_REF] created a new symbolic representation for time series (SAX) for indexing. [START_REF] Mohammad | Constrained motif discovery in time series[END_REF] proposed two algorithms called MCFull and MCInc that address constrained motif discovery problem. [START_REF] Castro | Multiresolution motif discovery in time series[END_REF] addressed motif discovery problem as an approximate top k-frequent subsequence discovery problem. [START_REF] Lin | Motif and anomaly discovery of time series based on subseries join[END_REF] presented an approach that uses subseries joins to get similarity among subseries of the time series. [START_REF] Armstrong | Unsupervised discovery of motifs under amplitude scaling and shifting in time series databases[END_REF] developed the algorithm MD-RP for unsupervised motif discovering in time series. [START_REF] Narang | Real-time approximate range motif discovery & data redundancy removal algorithm[END_REF] designed the new sequential and parallel Motif discovery and data deduplication algorithms based on bloom filters.

Finally, Regarding variable-length motif discovery, [START_REF] Wilson | The motif tracking algorithm[END_REF] proposed the Motif Tracking Algorithm (MTA) that uses a small number of parameters based on the implementation of the Bell immune memory theory. [START_REF] Yankov | Detecting time series motifs under uniform scaling[END_REF] presented a novel algorithm that discovers motifs in time series with invariance to uniform scaling.

It enables to reduce parameters such as motif length. [START_REF] Nunthanid | Discovery of variable length time series motif[END_REF] described the VLMD motif discovery algorithm that does not require the motif length parameter.

Such an algorithm automatically returns motif lengths from all possible sliding window lengths reducing a set of possibilities of the sliding window lengths. Nunthanid et al.

[2012] presented the k-Best Motif Discovery (kBMD) algorithm that is parameter-free. It produces a set of the best motif that is ranked by a scoring function based on similarity of motif locations and shapes. [START_REF] Mueen | Enumeration of time series motifs of all lengths[END_REF] proposed the MOEN, an exact free-parameter algorithm to enumerate motifs that is faster than brute-force approach due to a novel bound on the similarity function that uses only linear space. [START_REF] Mohammad | Exact discovery of length-range motifs[END_REF] proposed an extension of the MK algorithm called MK++ to handle multiple motifs of variable lengths considering maximum overlap of subsequences.

Finally, when it comes to space modeling, [START_REF] Du | Migration motif: A spatialtemporal pattern mining approach for financial markets[END_REF] modeled space by discrete attributes that resemble states of an object. In the context of their paper, they refer to the state of companies in the stock market. It is, in fact, a state-space model [START_REF] Shumway | Time Series Analysis and Its Applications: With R Examples[END_REF] where a trajectory is the registration of state transitions. In this way, it differs significantly from our work, since such a phenomenon may not be constrained in space and time.

The approaches presented in the literature review propose to solve the problem of discovering patterns only in time series. We did not find studies that propose to solve the identification of patterns in space-time series. To the best of our knowledge, this is the first solution to address the problem of identifying frequent sequences constrained in space and time.

3-Problem Statement

The patterns discovery approaches presented in the literature review propose to solve the problem of discovering patterns on time series. In the context of spatial-time series, we observe a more complex scenario due to spatial constraints. Considering a dataset containing spatial-time series, each spatial-time series ST s has a position in space. If we apply to this scenario a traditional known pattern discovery method on each spatial-time series, the patterns found will be in the same spatial-time series only. Also, even when some patterns are discovered, considering the entire dataset, those are not fully explored including subsequences appearing in neighboring spatial-time series are not discovered as patterns.

Depending on the dataset, such similar subsequences in neighboring time series can correspond to some relevant information. Discovering and grouping patterns in spatialtime series datasets can address some real-world problems. Such scenario was not studied in previous works as discussed in Section 2.4. The problem formalization for this new scenario is presented as follows.

A spatial-time series dataset (for short, dataset) S is a set of spatial-time series st. We are interested in finding patterns that occur in a constrained space and time. In our work, sequences may only be frequent inside spatial-time parallelogram (for short, block).

A block b is a couple ({st}, i) where {st} is a subset of neighboring spatial-time series and i is a time interval. The size of a block b is the product of the number of spatial-time series by the interval length:

|b| = |{st}| • |i|.
Let B be a partition of S into blocks b. Let and  be two support values such that . A subsequence q is a spatial-time pattern if and only if there exists a block b such that q is included at least times in it and q occurs in at least  different spatial-time series inside b.

From the definition above, the problem can be summarized as the discovery of patterns in restricted spatial-time series dataset. To address the problem, we propose two approaches that are discussed in the following chapters.

4-Combined Series Approach (CSA)

The motif discovery approaches presented in the literature review propose to solve the problem of discovering motifs on time series. In the context of spatial-time series, we observe a more complex scenario due to spatial constraints. In this chapter, we present the CSA approach to discovery space-time motifs.

In order to highlight this challenging problem, Figure 3a shows a synthetic dataset, containing twelve spatial-time series (ST 1 • • • ST 12) where each spatial-time series ST i has a position in space. Figure 3b presents a flat representation of the this dataset. The ordering of time-series obeys their spatial placement. For example, ST 2 is both close to ST 1 and ST 3.

If we apply to this scenario a known motif discovery method on each spatialtime series for a support 2, we can only observe the motifs which are marked as green worm-like shape found only in ST 3 as shown in Figure 3. Also, even when some motifs are discovered, considering the entire dataset, those motifs are not fully explored:

there are many other equivalent worm-like shapes that are not discovered, although appearing in close spatial-time series (ST 2, ST 4). It is also possible to observe that similar subsequences appearing in neighboring spatial-time series are not discovered as motifs.

They are depicted in Figure 3 as orange trapezium-like and red stripe-like motifs.

Depending on the dataset, such similar subsequences in neighboring time series can correspond to some relevant information. Discovering and grouping motifs in spatialtime series datasets can address some real-world problems. Such scenario was not studied in previous works as discussed in Section 2.4.

We are interested in finding motifs that occur in a constrained space and time.

In our work, sequences may only be frequent inside spatial-time blocks, where we find that q is included at least times in it and q occurs in at least  different spatial-time series inside b.

From the definition above, the problem can be summarized as the discovery of spatial-time motifs in a spatial-time series dataset. To address the defined problem, we developed the Combined Series Approach (CSA).

4.1-General Principle

The Combined Series Approach (CSA) is organized in three main steps: (i) for each m i 2 stmotif s do

ent i = P |ft(m i )| k=1 ⇣ ft(m i ) k n • log 2 ⇣ ft(m i ) k n ⌘⌘ O i occurrences(m i ) occ i log 2 (O i ) prox i 1 aw(mst(wam(O i ))) rank = proj(norm(ent, occ, dist))
return order(stmotif s, rank)

4.2-Normalization & SAX indexing

The first step of the CSA, described by the normSAX function of Algorithm 4, applies z-score data normalization in the entire dataset. Right after normalization, SAX indexing method is applied for a given alphabet a. It transforms the numeric data from S into letters according to the data distribution, as described in Section 2.1. The output of such transformation is DS.

4.3-Spatial-time Motif Discovery

The second step of CSA corresponds to discoverST M otif s function. In line 11, the indexed spatial-time series dataset S is partitioned into blocks (B). These blocks are created based on spatial block size (sb x , sb y ) and temporal block size (tb). The spatial block size (sb x , sb y ) delimit the number of neighboring spatial-time series inside each block. The tb specifies the time interval for subsequences of spatial-time series. B is the partition of S into a set of blocks {b i,j,k }. Formally, each block b i,j,k contains sb

x • sb y • tb observations, 8i 2 [1, |st.t| tb ], 8j 2 [1, |S| sbx ], 8k 2 [1, |S| sby ].
Each block b i,j,k contains sb x • sb y subsequences q m , such that q m = seq tb,(i 1)•(tb)+1 (S (j 1)•sb+m .t), 8m 2 [1, sb].

In line 14, all sequences inside a block are combined into a single time series cs, such that cs is the concatenation of sequences inside the block b i,j,k . Formally,

cs = q 1 k • • • kq m and |cs| = P m i=1 |q i | = sb x • sb y • tb.
The discover function (line 15) checks all subsequences of size w in cs. It applies an adapted algorithm [START_REF] Mueen | Enumeration of time series motifs of all lengths[END_REF] for time series identification of motifs of length w. It starts applying a hash function for registering the positions of each individual subsequence s i . If the number of occurrences of s i is greater than , s i is a temporal motif and included at motif s. Then, in line 16, motif s are validated according to both and . It checks the number of distinct spatial-time series for them is greater or equal to . It is worth mentioning that any motif whose sequence appears distributed between neighboring subsequences of a block (for example, q k and q k+1 ) are fake occurrences and not considered during and  validation. Motifs that validates both and  are added at stmotif s.

4.4-Rank motifs

Since the number of motifs can be high, especially when working with larger alphabets, it is important to establish ways to rank them in a way that more "interesting" ones are presented first. The third step of CSA, described by the rankST M otif s function of Algorithm 4, makes a balance among three criteria: (i) the number of occurrences (significant higher occurrences are better); (ii) proximity (occurrences that are close to one another are better than the ones that are sparsely distributed in the dataset); (iii) entropy (higher entropy contains more information, which makes it more interesting).

Each motif corresponds to a sequence of SAX observations. All motifs that are discovered inside discoverST M otif s are local block motifs. At group function (line 2), occurrences of motifs sharing the same sequence are grouped as long as they occur in neighboring blocks. Then, for each group of motifs m i , metrics for ranking them are computed. In line 21, the entropy of a motif m i of size n is computed (ent i ). The ent i is based on information theory and uses the frequency table (fm) for the characters presented in a motif [START_REF] Shannon | A Mathematical Theory of Communication[END_REF] and is described in line 21. The higher is the entropy, the higher is the information that motif m i encodes.

At line 22 the set of occurrences O i for the motif m i is obtained. Then, at line 23, the impact of the number of occurrences (O i ) of the i-th motif in a logarithm scale is computed (occ i ). This enables that only a significantly different number of occurrences becomes apparent.

In line 24, the weight of the occurrences according to their proximity is computed.

Consider the pairs of position and time for the set of occurrences O i of a motif m i discovered in neighboring blocks. The distance between all these pairs is represented as a weighted adjacent matrix (wam). Then, the minimum spanning tree (mst) is built from the wam. Finally, the average weight (aw) for the edges of the mst is computed. Thus, prox i establishes the reciprocal measure for aw for the motif occurrences. The closer this measure is to 1, the closer are the occurrences in establishing a spatial-temporal pattern.

Once the entropy (ent i ), the amount of occurrences (occ i ), and the proximity (prox i ) has been computed for each motif, the ranking procedure can be applied. During ranking, each of these dimensions are normalized using min-max and projected into the unit vector that combines these three dimensions. Such projection provides a balance among these dimensions. The closer the projection of a motif m i is to (1, 1, 1), the better ranked it is.

Function rankST M otif s returns the stmotif s ordered according to the computed rank.

5-Constrained Spatio-Temporal Matrix Profile (CST M P )

The traditional methods of identifying motifs (chapter 2) are restricted to the analysis of time series, not identifying spatially neighboring motifs when applied to space-time series. In the previous chapter, we introduced the Combined Series Approach (CSA), a method capable of discovering and grouping motifs in spatial-time series datasets. However, as observed, the CSA has some restrictions due to its modeling. With the use of non-overlapping blocks, as defined in chapter 3, the motifs present in intercession of blocks are not correctly identified. Besides, the CSA restricts the analysis of neighboring series that are only in the same spatial dimension.

To deal with these restrictions, we introduce a simple and efficient identification algorithm to discover motifs restricted in space-time, called Constrained Spatio-temporal Matrix Profile (CST M P ), and conduct computational analyzes to measure the assertiveness and performance. Our method can identify and group similar spatial-time motifs that are density-reachable. CST M P combines an evolution of the Matrix Profile approach for spatio-temporal data with an incremental distance computation strategy using Euclidean distance.

The overall method can be seen as a motif spatial-temporal identification and grouping algorithm, where initially, the space-time series sts are grouped given the distance radius to their neighbors. For each serie st and the set of its neighbors, the CST M P incrementally selects a block of subsequences from these series in a time interval i, where it applies motif discovery. Finally, since all the series were visited, the motifs found are ranked according to their frequency. As demonstrated by our experiments on various datasets, CST M P identifies space-time motifs with significantly higher quality than those provided by previous approaches. Its computational time is also lower than the other approaches, including the CSA.

Before presenting CST M P , some definitions are necessary. A block b is a couple (t, s) where t is the time interval and s is the spatial location. The size of a block b is the product of range size with interval length: |b| = |b.r| • |b.i|. We define the set of all possible blocks over D as P B(r, g).

5.1-General Principle

The general scheme is given in Algorithm 25. The spatial-time series dataset is a set of series where each spatial-time series st can be described as a pair (t, p), such as a time series t with an associated position p (2.1). Based on p, the algorithm first calculates the distance between all series. Then, for each st series, a set is created with the series that is up to radius of sts n , given by neighborhood function (line 3-5). All these defined sets are organized in ST G. For each of the neighboring series groups group of the set ST G a for each loop (lines 7-19) performs a search for the frequent motifs. Each series in the set of neighbors, if it has not yet been marked as visited (line 9), is traversed in an iterative way (lines 8-22). At each iteration, the coreIndex element is defined (line 11), generating the spatio-temporal block (line 12). All sequences internal to the block are then generated in function generateSequences.

The AAM P function is then applied to blockSeq (line 14), calculating the matrix profile and generating all pairs with minimum distance from each other. From this set, the even sequences of the element coreIndex are then selected. If they have a quantity greater than the threshold defined in (line 15), they are added to the group motif Group of the element coreIndex. Finally, the groups of motifs are ranked according to their frequency (line 24).

Block Search

In each generated block, we want to identify the subsequences that can be reached by the coreIndex element. We understand that these subsequences are those that, among all the subsequences in the block, have the shortest distance to the CI element, thus being most similar. For this purpose an algorithm must 1) incrementally calculate the distance between all sequences and 2) select the subsequences that have the shortest distance for the coreIndex element.

The goal of blockSearch Algorithm 6 is to calculate the distance between the subsequences and identify the most similar of cI. For this, first, ST AAM P Algorithm 28 calculate the distance profile between all the sequences of the block (line 2). Then, a search is performed on the output looking for the subsequnces with the shortest distance to the CI element (line 3-7). As a result, a list of subsequences is returned. [START_REF] Akbarinia | Efficient Matrix Profile Computation Using Different Distance Functions[END_REF] introduces the AAM P , a simple but efficient algorithm for computing matrix profile with the pure Euclidean distance. AAM P is executed over a time series in a set of iterations, such that in each iteration the distance of subsequences is computed incrementally, as presented in Chapter 2. Since AAM P is a matrix profilespecific approach for time series, we develop the ST AAM P , presented in Section 5.1.1, an adaptation of AAM P for our space-time series context. In this way, we can perform the all-pairs-similarity-search in sequences of neighboring space-time series. ST AAM P has a worst-case complexity of O(n ⇥ (n m)) with small constants, where n is the number of sequences in the block and m the sequence length. The ST AAM P the algorithm receive as input a set the subsequences and the sequence length ws. It performs n iterations using a variable k (1  k  n), where n is the number of subsequences to be analyzed (Line 5). In each iteration k, the algorithm compares each subsequence T i,m with the subsequence that is k positions far from it, i.e., T i,m+k . To do this, ST AAM P firstly computes the Euclidean distance of the first subsequence, i.e., T 1,m , with the one that stars at position k, i.e., T k,m . This first distance computation is done using the normal formula of Euclidean distance (Line 7). Then, in a sliding window, the algorithm incrementally computes the distance of other subsequences with the subsequences that are k position far from them, and this is done by using the incremental euclidean distance in O(1) (Line 17). If the computed distance is smaller than the previous minimum distance that is kept in the matrix profile SM P , then the smaller distance is saved in the matrix profile (Line 18-26).

Algorithm 7 -STAAMP Input: blockSeq: set of subsequences; ws: sequence length; SM P : spatial matrix profile Output: SM P : Spatial Matrix Profile; begin n size(blockSeq)

for i = 1 to n do SM P [i] 1 end for k = 1 to n do dist Euc Distance(T 1,ws , T k,ws ) if dist < SM P [1].d then SM P [1].n k SM P [1].d dist end if dist < SM P [k].d then SM P [k].n 1 SM P [k].d dist end for i = 2 to n ws + 1 k do dist = p (dist 2 (t i 1 t i 1+k ) 2 + (t i+ws 1 t i+ws+k 1 ) 2 if dist < SM P [i].d then SM P [i].n i + k SM P [i].d dist end if dist < SM P [i + k].d then SM P [i + k].n i SM P [i + k].d dist end end end end

6-Experimental Evaluation

In this chapter, an evaluation of the methods presented in this work is provided. We report the experimental results that show the effectiveness of CSA and CSTMP in the task of identifying motifs restricted in space-time in different datasets. We compared the results with the Matrix Profile, the state-of-the-art approach for detecting motifs in time series. In addition, we suggest a baseline approach, where we combine the Matrix Profile technique with the DBSCAN algorithm, adapting the approach to the spatio-temporal scenario.

In Section 6.1 below, the datasets used are presented, describing their characteristics and mapped results. Section 6.2 presents the comparative analysis of the methods applied to a synthetic dataset, detailing the employment and characteristics of these approaches. Finally, in Section 6.3, a comparative and sensitivity analysis of approaches is conducted in the seismic dataset, providing more information on the approach's behavior in real data.

6.1-Datasets

A synthetic and a real seismic spatial-time dataset have been used for evaluation.

Despite their size differences, these datasets allow us to analyze different types of motifs restricted in space-time and provide a good discussion about each approach and its effectiveness. We can better explain about datasets as follows:

Syntetic data: This is a dataset designed to better elucidate and understand the problem of identifying restricted motifs in space-time. Each column is a spatial-time series (varying from positions 1 to 36) with 40 observations in time. This dataset contains a set of 108 mapped occurrences, each with size 4 (ws = 4). Figure 4 shows the identified spatialtime motifs series and highlights three motif groups. Each group allows an analysis of the spatio-temporal distribution of the identified motifs, being a set more frequent in space (red), a second set with more frequency in time (green), and a third group homogeneously distributed both in space and time (green, blue). waves with energy sources that disturb the medium, such as explosives or air guns (called seismic shots), and record the waveforms of the various interfaces in the subsoil using sensors (geophones or hydrophones) in that acquisition air guns and hydrophones were used. The generated wave propagates through the interior of the Earth and the Sea. The partially reflected waves are used to find interfaces between layers that have significant contrasting elastic properties. The arrival time of each reflection is related to the propagation velocities of the seismic wave in each layer. In a first approximation, the recorded amplitude is related to the contrast of the acoustic impedance, a product of velocity and density of the layers that define the interface.

In the F3 Block dataset, each spatial-time series has a position in which the hydrophone is placed. The dataset is organized into inlines (direction of the ship navigation).

We selected inline 401 since it has been mapped by seismic specialists who have annotated some relevant information. Figure 5 presents inline 401, which consists of 920 spatial-time series with 440 observations in each. The horizontal axis represents the position of the receivers, and the vertical axis represents the time, which is also related to the depth at the subsoil. The location of seismic horizons noted by specialists is marked in the data.

Figure 5 -Seismic dataset with the mapped horizons

6.2-Analysis on the synthetic dataset

First, we conducted the experiments on the synthetic dataset, which, although less complex, allows us to understand the proposed problem and the challenge of the proposed solution. The main objective is to study the number of motifs discovered and their occurrences and understand the computational cost.

We conducted our experiments by comparing the performance of our spatiotemporal motif identification methods (CSA [START_REF] Borges | Spatial-time motifs discovery[END_REF] and CSTMP) with the variations of the Matrix Profile [START_REF] Yeh | Time series joins, motifs, discords and shapelets: a unifying view that exploits the matrix profile[END_REF] (MP 1 and MP 2 ), in addition to two baseline approaches (B 1 and B 2 ) where we combine the Matrix Profile results using the DBSCAN algorithm. In Table 1, we list the approaches and their corresponding variations that are used in the discussion of this section. The CSA and the Matrix Profile implementation are available as an R Package in STMotif1 and tsmp2 , respectively. The CSTMP is available on the github platform3 . Matrix Profile is a technique that works for all-pair-similarity-search across a time series, as described in the section 2.1. Matrix Profile is a technique that works for all-pairsimilarity-search across a time series, as described in the section 2.1. As it works only with time series, some adaptations are necessary to apply the technique to spatial-time series. At MP 1 , we intuitively apply the technique to each series separately requesting one motif per series. At the end of the process, we have grouped all identified motif pairs into one large set. In Figure 6, we present the result of applying the MP 1 approach to the syntetic data set. The approach found 36 motifs (72 occurrences), distributed by the data, with a high error rate, correctly identifying only 14 occurrences. Another way to apply the Matrix Profile, proposed in MP 2 , is to combine all spatialtime series (STS) into a single series so that the end of the sts k series is concatenated with the beginning of sts k+1 . In Figure 7, we present the result of applying the MP 2 approach to the syntetic data set, requesting 54 motifs (108 occurrences). The result is worse than that presented in MP 1 , featuring a large number of motif sets, correctly identifying only 12 occurrences.

Figure 7 -MP 2 -Matrix Profile on syntetic dataset By conducting the experiments, it is possible to analyze that even increasing the number of requested motifs, both in approaches MP 1 and in MP 2 , they do not accurately detect motifs, gradually increasing the recall and decreasing the accuracy. The results become irrelevant since they present many errors in addition to identifying motifs that do not respect the space-time constraint.

In the face of these problems, as an alternative to remove outliers and restrict the observations identified in space and time, we present a baseline approach that combines the Matrix Profile approach with the DBSCAN clustering algorithm. Given the motifs identified by the Matrix Profile, the DBSCAN groups those close together into clusters and mark as outliers those who are distant, respecting the radius of a neighborhood ✏ and a minimum number of points minPts. For the analysis in synthetic dataset, we considered a lower constraint, ✏ = 2, minPts = 3.

In Figure 8, we present the result of Baseline 1 approach, applying DBSCAN to MP 1 results, requesting 1000 motifs. Likewise, in Baseline 2 , we use the results of MP 2 , requesting also 1000 motifs, shown in Figure 9. DBSCAN can identify and remove outliers, but the results show a high error rate, with low accuracy. Even performing a gradual increase in the number of motifs requested, in both approaches, the results remain with low precision, further decreasing the accuracy.

The Combined Series Approach (CSA) is an approach to discover and classify The CSTMP approach, also proposed by this work, is developed specifically for space-time data. For the application of the technique in synthetic data, we used as a

6.3-Analysis on the seismic dataset

In this section, we discuss the preliminary results of the approaches presented in this work in discovering spatial-time restricted motifs using the inline 401 of the Netherlands seismic spatial-time series dataset.

First, we evaluate the two suggested baseline approaches (Baseline 1 and Baseline 2 ).

As input, Baseline enables users to set the following parameters: word size, which is the word size to be used by the Matrix Profile, varying between values 4 to 7. The DBSCAN receives from the Matrix Profile a set of positions of the found motifs and the parameters eps and minP ts, generating a set of motif clusters. The eps parameter corresponds to the radius size between two motifs so that one is considered a neighbor to the other, and the minP ts parameter is the minimum number of motifs in a neighborhood to be considered a central point. A list of the parameters used is shown in table 3 below. In the first case, using the parameter eps = 24, some larger sets are formed, but with a low recall, as many false-positive motifs are detected. In the second case, duplicating the eps parameter, we have a similar situation, where a large number of false-positive motifs are detected, without mapping and identifying the horizons. In this analysis, the goal is to study the number of discovered motifs and their occurrences and computational time as we vary block size (tb and sb), word, , and .

To evaluate the influence of block orientation, we set three orientations: vertical rectangle (tb = 40; sb = 10), square (tb = 20; sb = 20), and horizontal rectangle (tb = 10; sb = 40). For a fair comparison, all of them contain the same amount of observations.

Table 5 presents the overall performance of both traditional approach and CSA under different block orientation for all possible parameter combinations described in Table 4. The motifs column corresponds to the mean number of motifs whose occurrences were grouped with at least one neighboring block and contained more than seven occurrences (the maximum value adopted). In the case of the traditional approach, we considered it as a block of 440 temporal observations with one spatial-time series, so that the same grouping criteria could also be applied. The traditional approach, on average, discovered 43 different motifs under 449 sets of occurrences. It means that the same motif contains, on average, ten different spatial-temporal sets of occurrences. Also, the average discovery time and average time to rank motifs were, respectively, 1.8 and 2.0 minutes. The average elapsed time was 4.7 minutes, which also includes the time to do the data normalization and SAX encoding.

The time for discovering motifs was approximately the same for all configuration, except for Horizontal orientation. In this setup, as we increase the size of the word, there is a lower number of possible motifs to discover. It becomes unnecessary to check for motifs in between two consecutive spatial-time series. It makes less possible comparisons for this setup, also meaning that a lower number of motifs are discovered. However, all CSA block orientations discovered more motifs than traditional approach (the square had the better performance. It discovered more than 2.5 times more motifs than traditional approach).

Comparing the performance of different CSA orientations (Vertical, Square, and Horizontal), we may expect that typically Horizontal orientation might break temporal sequences. However, in our dataset, patterns often occurred in small time intervals spread in space. Such behavior justifies the better performance of Horizontal orientation over Vertical one. Additionally, Square orientation had a better balance between time and space and was able to identify more patterns. The choice of block orientation is fairly domain-dependent. Users may consider their knowledge about the data to set up this parameter.

Table 6 disclosures the results of Table 5 according to the word size. It presents the number of discovered motifs and the sets of occurrences, applying the same criteria used to produce Table 5. It can be observed that as we increase the word size, the number of discovered motifs decreases. The same behavior occurs to the set of occurrences.

The highest number of identified motifs occurred in CSA Square orientation for word size equals to four. Finally, the computation time (in minutes) for all discovered motifs also decreases as we increase the word size. It is due to the ranking function overhead. It has less impact on time when handling a lower number of occurrences. Also, as we increase  constraint, the number of occurrences also decreases.

Finally, we analyzed the top-k spatial-time motifs discovered using CSA Square block orientation for word size of four, fixing equals to three and  equals to three. In this configuration, as presented in Table 8, we computed the top-5 distinct motifs that accomplished the same criteria adopted to build Table 5.

The highest ranked motif (aagg) presented a good proximity value, an average The set of occurrences for each motif was plotted, as long as their ranking value were greater than 1.0. It can be observed that the occurrences of motifs matched more regions where seismic horizons are located.

It is worth mentioning that the ranking function was conceived for general purpose usage and did not focus on any aspect to target seismic horizons. Nevertheless, they were able to discover the majority areas in which seismic horizons were annotated.

CST M P is a hybrid approach that combines the features of a density-based clustering approach, such as DBSCAN, and motif identification in a local search. The 9. First, we study the effect of the parameters of CST M P applied to the seismic dataset, how they influence the quality of results and processing time. Through this analysis, we want to study the identified motifs, the number of occurrences and the computational time as we vary the desired amount , the radius size and the word size. The choice of radius size is based on the neighborhood to be investigated. We varied the radius size from 5 to 7 and measure the quality and associated time. The larger the radius, the larger the search area and thus the longer is the processing time. For an equal comparison, all of them used the same word size (ws = 4) and the same threshold ( = 3).

Table 10 presents the overall performance of CST M P with variations in radius size.

The motif column corresponds to the number of identified motif sets, where it maintains high similarity to each other (observing the minimum value = 3 occurrences by set).

The occurrences column corresponds to the total number of occurrences of the identified motifs. Lastly, the discovery time to identify motifs with this setting is presented. As the radius size increased, the time for discovering motifs also increased. This confirmation was already expected, since the increase in radius, with the consequent increase in the block, generates a proportionally greater number of comparisons between neighboring sequences.

Table 11 extends the results presented in Table 10 according to the radius size. For each radius and word size, it shows the number of identified motif sets and the number of occurrences, observing the minimum of = 3 occurrences per set. It is possible to observe that the increase in word size generates a small increase in the number of identified motifs.

This behavior occurs by generating small sets of motifs, with little similarity. Computation time is also presented, which grows as the radius is increased. Finally, Table 12 presents the influence of in the number of discovered motifs for the CST M P as the size of the radius increases. It is possible to observe that as we increase , lower number of occurrences are identified.

To assess the quality of the identified motifs, we traced two results, according to the ranking of the group of motif sets found. In Figure 22, we present the top motifs with

Figure 10 -Figure 11 -Figure 12 -Figure 17 -Figure 18 -Figure 19 -

 101112171819 Figure 1 -Seismic Interpretation

Figure 23 -

 23 Figure 23 -Top discovered motifs according to spatial extension, filtering

Figure 1 -

 1 Figure 1 -Seismic Interpretation (adapted from Borges et al. [2020] )

Figure 2

 2 Figure 2 depicts the application of the above definitions to a time series. The blue line represents a time series t, the red line represents a subsequence from the time series, and the green dashed lines are examples of some of the subsequences extracted from time series based on sliding windows.

Figure 2 -

 2 Figure 2 -An example of a time series, sub-sequences, and sliding windows[START_REF] Borges | Spatial-time motifs discovery[END_REF]

Finally, theP

  result P AB and I AB are returned in line 7. In this format, STAMP computes the MP for the general similarity join. It is possible to change the algorithm to compute the self-similarity join MP of a time series T A , just by replacing T B in line 2 with T A , replace B with A in line 5, and ignore trivial matches in D when performing ElementWiseMin in line 6. The overall complexity of the algorithm is O(n 2 log n) where n is the length of the time series. Since all subsequences are compared using the MASS algorithm, the n log n factor comes from the FFT subroutine. Algorithm 1 -STAMP (T A , T B , m) Input: Two time series, T A and T B Interested subsequence length m Output: A matrix profile P AB and associated matrix profile index I AB of T A join T AB , I AB ElementWiseMin(P AB , I AB , D, idx) 7 return P AB , I AB

Algorithm 2 -

 2 STOMP (T, m)Input: A time series T and a subsequence length m Output: Matrix profile P and the associated matrix profile index I of T

  introduced the Par-MK, Par-MK-SLB, and Par-MK-DLB, which are all parallel multi-threaded algorithms for exact motif discovery that focus on load balancing.[START_REF] Mueen | A disk-aware algorithm for time series motif discovery[END_REF] proposed a disk-aware algorithm to discover exact motifs in large time series databases.[START_REF] Cassisi | Motif Discovery on Seismic Amplitude Time Series: The Case Study of Mt Etna 2011 Eruptive Activity[END_REF] applied a motif discovery technique for an exact time series to study recurrent patterns in seismic amplitude time series of the Etna 2011 periodic eruptive activity.[START_REF] Chi | Finding time series motifs based on cloud model[END_REF] introduced a method based on cloud model theory to extract the top k-motifs.[START_REF] Truong | A fast method for motif discovery in large time series database under dynamic time warping[END_REF] proposed a fast method for motif discovery in time series based on Dynamic Time Warping distance.

Figure 3

 3 Figure 3 -(b)A synthetic dataset with twelve spatial-time series: ST 1 • • • ST 12. Traditional motif discovery algorithm applied in this spatial-time series dataset finds only the two green worm-like in ST 3 as motifs.

Figure 4 -

 4 Figure 4 -Synthetic dataset with identified motifs

Figure 6 -

 6 Figure 6 -MP 1 -Matrix Profile on syntetic dataset

Figure 8 -

 8 Figure 8 -Baseline 1

Figure 10

 10 Figure10shows the result of CSA 1 approach, using tb = 9 and sb = 10. For CSA 2 we use tb = 9 and sb = 10 and the result is shown in the figure11. For CSA 3 we use a vertical rectangle with tb = 9 and sb = 10 with the result shown in figure12. Table 2 presents the overall performance of the CSA under different block orientation. The results demonstrate a strong influence of the orientation of the blocks on the

Figure 10 -

 10 Figure 10 -CSA 1 -CSA on synthetic dataset -(sb ⇡ tb)

  minP tsnumber of minimum points required in the eps neighborhood for core points (including the point itself).

Figure 14 -

 14 Figure 14 -Baseline 1 (eps = 4; minP ts = 10) -Seismic Dataset

Figure 15 -

 15 Figure 15 -Baseline 1 (eps = 4; minP ts = 12) -Seismic Dataset

Figure 17 -

 17 Figure 17 -Baseline 2 (eps = 8; minP ts = 5)-Seismic Dataset

Figure 20 -

 20 Figure 20 -MSE for each alphabet size

  proximity and entropy values. The third place (aaag) was similar to the first motif, but with lower occurrences value. The fourth place (ggf a) compensated the low occurrences value with an excellent proximity value. Finally, the fifth place (egf a) is similar to the second, with a slightly lower proximity value.In order to have an intuition on the quality of the ranked motifs, we have plotted the top-ten discovered motifs as we see in Figure21(a), according to the ranking function, on top of the seismic dataset. The places where the motifs were plotted are in agreement with annotations from specialists where seismic horizons are located. Also the yellow ones are very close to a gas reservoir.In a complementary analysis, we sorted the motifs according to the number of occurrences. Figure21(b) plots the top-ten distinct motifs sorted by their occurrences.

Figure 21

 21 Figure 21 -(a) Top-ten discovered motifs according to the ranking function (b) Top-ten discovered motifs according to the number of occurrences, filtering the ones with ranking function lower than 1.0

  the highest number of occurrences. Then, in Figure23, we present the top motifs with greater spatial coverage. It can be observed that the identified motifs cover the regions of the mapped horizons, identifying, beyond the horizons, areas with potential accumulation of hydrocarbons.

Figure 22 -

 22 Figure 22 -Top discovered motifs according to the number of occurrences.

Figure 23 -

 23 Figure 23 -Top discovered motifs according to spatial extension, filtering those that cover a greater number of spatial-time series.

Table 10 -

 10 Overall performance of CSTMP under different radius size

	Table 1 -	Evaluated Approaches
	Table 2 -	Overall performance of CSA under different block orientation
	Table 3 -	Baseline Input Parameters
	Table 4 -	CSA Input Parameters
	Table 5 -	Overall performance of CSA under different block orientation
	Table 6 -	Summary of Discovered Spatial-Time Motifs for different block
		orientation and word size
	Table 7 -	Influence of and  in the number of occurrences in Square
		(20x20) setup with word size w = 4
	Table 8 -	Top five distinct motifs
	Table 9 -	CST M P Input Parameters

Table 11 -

 11 Summary of Discovered Spatial-Time Motifs for different radius

	and word size

Table 12 -

 12 Influence of in the number of motifs and occurrences with word

	size w = 4

  CSA is summarized in Algorithm 4. It takes as input a spatial-time series dataset S, a word size w, an alphabet size a, sb x , sb y and tb corresponding to spatial block sizes, temporal block sizes, and and  constraints.

	normalization & SAX indexing; (ii) discovery of spatial-time motifs; (iii) ranking of spatial-function CSA(S, w, a, sb x , sb y , tb, , ) DS normSAX(S, a) stmotif s discoverST M otif s(DS, w, sb, tb, , ) rstmotif s rankST M otif s(stmotif s) return rstmotif s function normSAX(S, a) Sz zscore(S) DS SAX(Sz, a) cs combine(b i,j,k ) motif s discover(cs, w, ) stmotif s validate(motif s, , ) [ stmotif s return stmotif s function rankST M otif s(stmotif s) time motifs. Algorithm 4 -Combined Series Approach stmotif s group(stmotif s)

return DS function discoverST M otif s(S, w, sb x , sb y , tb, , ) B partition(S, sb x , sb y , tb) stmotif s ; for each b i,j 2 B do

Table 1 -

 1 Evaluated Approaches

	Approach Variation Description
		MP 1	Applied to each ST-Series
	MP	MP 2	Applied to the concatenated series
		Baseline 1 MP 1 with DBScan
		Baseline 2 MP 2 with DBScan
		CSA 1	CSA with sb = tb
	CSA	CSA 2	CSA with sb > tb
		CSA 3	CSA with sb < tb
	CSTMP CST M P 1 CSTMP

Table 2 -

 2 Overall performance of CSA under different block orientation

	Block orientation	motifs	sets of occur.
	CSA 1 Square (9 x 10)	108	110
	CSA 2 Horizontal (9 x 4)	108	110
	CSA 3 Vertical (4 x 10)	21	108

Table 3 -

 3 Baseline Input Parameters

	Parameter	Description (explored values)
	ws	Length of motif word (from 4 to 7)
	eps	size (radius) of the epsilon neighborhood.

Table 4 -

 4 CSA Input Parameters

	Parameter	Description (explored values)
	alpha	Size of the alphabet for SAX indexing (fixed at 7)
	word	Length of motif word (from 3 to 7)
	tb x sb	Temporal and spatial block size (40x10, 20x20, 10x40)
		Minimum number of occurrences inside each block (from 2 to 7)
		Minimum number of spatial-time series with occurrences inside each block (from 1 to 5)

Table 5 -

 5 Overall performance of CSA under different block orientation

	Block orientation	motifs	sets of occur.	discovery time (min)	ranking time (min)	elapsed time (min)
	Traditional (440x1)	43	449	1.8	2.0	4.7
	CSA Vertical (40x10)	85	673	1.6	1.8	4.2
	CSA Square (20x20)	114	772	1.4	1.6	3.8
	CSA Horizontal (10x40)	105	705	0.9	1.2	2.9

Table 6 -

 6 Summary of Discovered Spatial-Time Motifs for different block orientation and word sizeTable12presents the influence of and  in the number of discovered motifs for the CSA according to the CSA Square block orientation for word size equals to four. It is possible to observe that as we increase , lower number of occurrences are identified.

	Block Orientation	word motifs set of occurences total time (min)
		3	139	95862	9.5
		4	65	6809	5.4
	Traditional (440x1)	5	7	369	3.0
		6	2	73	2.7
		7	1	17	2.6
		3	168	62278	8.0
		4	163	13980	4.7
	CSA Vertical (40x10)	5	60	2988	3.3
		6	23	761	2.7
		7	11	229	2.5
		3	184	62324	6.7
		4	221	16887	4.5
	CSA Square (20x20)	5	103	4182	3.1
		6	42	1157	2.4
		7	19	352	2.1
		3	187	52199	5.5
		4	219	12901	3.7
	CSA Horizontal (10x40)	5	89	2918	2.3
		6	25	628	1.6
		7	7	149	1.2

Table 7 -

 7 Influence of and  in the number of occurrences in Square (20x20) setup with word size w = 4 value, and a high occurrences value. Such combination produced a rank value of 1.57. The second place (df ge), although exhibiting low occurrences value, has a good

		2	3	4	5	6	7
	1 42725 30052 21349 13559	9621	6959
	2 42253 29938 21297 13527	9589	6927
	3	-	29640 21191 13461	9530	6895
	4	-	-	20073 13184	9368	6758
	5	-	-	-	11900	8800	6490
			Table 8 -Top five distinct motifs
	motif proximity	entropy	occurrences rank
	aagg		0.74	1.0		8.28	1.57
	df ge		0.83	2.0		3.16	1.46
	aaag		0.85	0.8		7.06	1.45
	ggf a		1.00	1.5		3.17	1.40
	egf a		0.75	2.0		3.17	1.39

entropy

Table 9 -

 9 CST M P Input Parameters

	Parameter	Description (explored values)
	ws	Length of motif word (from 4 to 7)
	radius	Size of the radius for local search (from 5 to 7)
		Minimum number of occurrences inside each block (from 3 to 7)

Table 10 -

 10 Overall performance of CSTMP under different radius size

	Radius size	word size	motifs	occur.	discovery time (min)
	5 (11 x 6)	4	1596	8651	2.8
	6 (13 x 7)	4	1745	9564	3.6
	7 (15 x 8)	4	2092	11745	4.5

Table 11 -

 11 Summary of Discovered Spatial-Time Motifs for different radius and word size

	Radius size word motifs set of occurences total time (min)
		4	1596	8651	2.8
		5	1651	9169	3.0
	5 (11x6)	6	1659	9309	3.3
		7	1679	9628	3.6
		4	1745	9564	3.6
		5	1826	10367	3.8
	6 (13 x 7)	6	1946	11121	3.9
		7	2001	11756	4.1
		4	2092	11745	4.4
		5	2146	12359	4.5
	7 (15 x8)	6	2237	13079	4.7
		7	2254	13506	4.9

Table 12 -

 12 Influence of in the number of motifs and occurrences with word size w = 4

	Radius	3	4	5	6	7
	5	1596 (8651)	210 (1377)	63 (667)	5 (52)	2 (27)
	6	1745 (9564)	331 (2232)	54 (340)	5 (44)	1 (15)
	7	2092 (11745) 474 (3013)	51 (354)	4 (36)	-

https://cran.r-project.org/web/packages/STMotif/index.html

https://cran.r-project.org/web/packages/tsmp/index.html

https://github.com/heraldoborges/cstmp

ACKNOWLEDGMENTS

apoio da Coordenac ¸ão de Aperfeic ¸oamento de Pessoal de Nível Superior -Brasil (CAPES)a https://team.inria.fr/zenith/ b érie temporal. Uma área relevante que est á sendo explorada na an álise de s éries temporais é a de descoberta de padr ões. Padr ões s ão subsequ ências de s éries temporais relacionadas a algumas propriedades ou comportamentos especiais. significativo de vezes em s éries temporais é denominado motif. Vários fen ômenos importantes de uma s érie temporal apresentam comportamentos diferentes quando observados em pontos do espac ¸o (por exemplo, s éries coletadas por sensores e IoT) e s ão melhor modelados como s éries espac ¸o-temporais, em que cada s érie temporal é associada a uma posic ¸ão no espac ¸o. Um padr ão espac ¸o-temporal é uma sequ ência de eventos que s ão limitados no espac ¸o e no tempo. Encontrar padr ões que s ão frequentes e restritos em um espac ¸o e tempo pode nos permitir compreender como um fen ômeno ocorre.

Diversos trabalhos foram desenvolvidos com o objetivo de identificar motifs em s éries temporais, entretanto n ão foram identificados trabalhos que abordassem t écnicas para dados espac ¸o-temporais. Nesta tese comparamos diferentes abordagens de identificac ¸ão de motifs em s éries temporais com suas principais diferenc ¸as. Propomos dois m étodos para a identificac ¸ão autom ática de motifs restritos no espac ¸o-tempo em s éries espac ¸o-temporais, o CSA e o CST M P . Comparamos experimentalmente os m étodos propostos com dois outros m étodos alternativos: a t écnica Matrix Profile e a combinac ¸ão da t écnica Matrix Profile e DBScan. Nossos resultados mostram écnicas estado da arte para s éries temporais e suas adaptac ¸ões para s éries espac ¸o-temporais, sendo avaliados em dois datasets. Espac ¸o-Temporais; Motifs; Sequ ências Restritas

parameter, the word size with ws = 4 and radius = 7. The result of CSTMP is shown in the Figure 13. The approach is able to identify a greater number of motifs than the previous approaches, finding a set of 108 motifs, without making any mistakes. An important point is that the approach is able to identify motifs that were not identified by the CSA approach.

7-Conclusion

Many applications observe phenomena whose values vary according to space and time dimensions. Discovering phenomena which are dependent on the occurrence in space and time requires extensions to traditional techniques adopted in time series analysis. In this work, we present a challenging problem with high impact potential: the discovery of motifs restricted in space and time. We tackle this problem by introducing two novel approach for spatial-time series motif discovery, the CSA (Combined Series Approach) and the CSTMP (Constrained Spatio-Temporal Matrix Profile). To the best of our knowledge, this is the first work to propose a complete approach for spatial-time motif discovery.

CSA supersedes traditional techniques when discovering spatial-time motifs, as it has been shown in our experimental evaluation. Additionally, CSA exhibits two major strengths points. Firstly, it is a divide-and-conquer algorithm that starts by discovering motifs inside a given spatial-time block. These blocks are then merged if neighboring blocks increase the number of occurrences of the discovered motifs. Such a technique makes the algorithm resilient to the initial block selection. Secondly, once the blocks have been defined, the algorithm is independent of the motif discovery algorithms applied.

Such property enables exploring different motif discovery algorithms, such as Random

Projection and Matrix Profile, to space-time series discovery.

We also propose CST M P , an approach inspired by the Matrix Profile and DBScan approaches. Our method can identify and group similar spatial time motifs that are reachable by density. CST M P handles some restrictions found in CSA, avoiding the problem of non-overlapping blocks. Through CST M P it is also possible to perform data analysis with two spatial dimensions and one temporal dimension. The approach achieved better results than traditional techniques such as Matrix Profile, even in a tailored approach, with less processing time in many scenarios.

We have evaluated CSA and CST M P against traditional approach using both synthetic and seismic dataset. The two approaches was able to identify more motifs and occurrences than the traditional approach. Also, the identified motifs were also well ranked considering both spatial-time constraints and number of occurrences.

Although the assessments were conducted using seismic data, the proposed approaches were conceived generically and applied in different scenarios with spatiotemporal data. Due to the potential of the techniques, opportunities open up to explore other real-world applications modeled as spatio-temporal series (such as ocean surface temperature data and pandemic propagation data). There are also opportunities to explore different classification functions to address domain-specific problems.