Hugo Alatrista-Salas
email: hugo.alatrista-salas@teledetection.fr.

Sandra Bringay

Frédéric Flouvat

Nazha Selmaoui-Folcher

Maguelonne Teisseire

Spatio-sequential patterns mining: Beyond the boundaries

Keywords: Sequential patterns, spatiotemporal data mining, health risk management

Data mining methods extract knowledge from huge amounts of data. Recently with the explosion of mobile technologies, a new type of data appeared. The resulting databases can be described as spatiotemporal data in which spatial information (e.g., the location of an event) and temporal information (e.g., the date of the event) are included. In this article, we focus on spatiotemporal patterns extraction from this kind of databases. These patterns can be considered as sequences representing changes of events localized in areas and its near surrounding over time. Two algorithms are proposed to tackle this problem: the first one uses a priori strategy and the second one is based on pattern-growth approach. We have applied our generic method on two different real datasets related to: 1) pollution of rivers in France; and 2) monitoring of dengue epidemics in New Caledonia. Additionally, experiments on synthetic data have been conducted to measure the performance of the proposed algorithms.

Introduction

New mobile technologies enable information to be linked with temporal and spatial characteristics. Data mining methods must be able to fulfill the new needs generated by spatiotemporal data. For instance, the study of phenomena like dengue fever epidemics or watercourses pollution become critical due to their complex dynamic. 1 In the case of dengue epidemics, public health experts know that the evolution of the disease depends on environmental factors (e.g., climate, areas with water points, mangroves, etc.) and on interactions between human and vector transmission (e.g., the mosquito that carries the disease). However, the impact of environmental factors and their interactions remain unclear.

In this context, methods for mining spatiotemporal data provide very relevant solutions through identification without a priori hypothesis of relationships between variables and events characterized in time and space. For example, in our context, we will discover combinations of changes in environmental factors that lead to epidemic peaks in specific spatial configurations. To extract this kind of information, [START_REF] Cao | Mining frequent spatio-temporal sequential patterns[END_REF][START_REF] Giannotti | Trajectory pattern mining[END_REF][START_REF] Wang | Mining frequent trajectory pattern based on vague space partition[END_REF] Trajectory Spatiotemporal sequence Support [START_REF] Shekhar | Discovering Spatial Co-Location Patterns A Summary Of Results[END_REF] Set of features Spatial co-location Conditional probability [START_REF] Celik | Mixed-drove spatiotemporal co-occurrence pattern mining[END_REF] Set of features Spatial co-location Temporal and spatial prevalence [START_REF] Pei | Mining sequential patterns by pattern-growth: The prefixspan approach[END_REF] Set of features Temporal event Support [START_REF] Tsoukatos | Efficient mining of spatiotemporal patterns[END_REF] Set of features Spatiotemporal event Support [START_REF] Wang | Mining generalized spatio-temporal patterns[END_REF] Sequences of features Spatiotemporal spread of objects Temporal and spatial support [START_REF] Huang | A framework for mining sequential patterns from spatio-temporal event data sets[END_REF] Sequences of features Spatiotemporal spread of objects Sequence index [START_REF] Mohan | Cascading spatio-temporal pattern discovery: A summary of results[END_REF] Set of features Spatiotemporal event Cascade participation index to extract global sequence of features. However, they study events one after another. They do not take into account interactions such as: often heavy rain and the occurrence of ponds are presented before the development of mosquito nests. Celik et al. [START_REF] Celik | Mixed-drove spatiotemporal co-occurrence pattern mining[END_REF], proposed the concept of Mixed-Drove Spatiotemporal Co-occurrence Patterns, i.e., subsets of two or more different event-types whose instances are often located in spatial and temporal proximity (e.g., an event-type is heavy rain and an instance is heavy rain in zone Z1 the 10/17/2013). For similar reasons than Huang, they have proposed a specific monotonic composite interestingness measure based on spatial and temporal prevalence measures. However, they do not extract the frequent evolutions of even-types over time (events of each instance occur necessarily in the same time slot). For example, we can only extract patterns such as: heavy rain, ponds and development of mosquito nests are frequently found together in lots of time slots.

On the other hand, Mohan et al. [START_REF] Mohan | Cascading spatio-temporal pattern discovery: A summary of results[END_REF] have proposed a new spatiotemporal pattern called Cascading Spatiotemporal Pattern (CSTP) that represents a partial ordered subset of event-types whose instances are located together and occur serially. In our context, an example of CSTP is: often, after heavy rain, a mosquitoes nest and some cases of dengue are present in a zone. This kind of patterns, which are partial ordered -as opposed to sequential patterns that are fully ordered -does not capture the interactions between a subset of features occurring in a particular area with others around. Finally, approaches proposed by Wang, Huang, Celik and Mohan can not capture the evolution of areas with regard to their set of event-types and the sets of event-types of their neighbors.

Table 1 presents a resume of related work considering the pattern type, the spatiotemporal properties and the interestingness measure.

In this paper, we describe a method for extracting spatiotemporal sequences of patterns (i.e., sequences of spatial sets of events) called Spatio-Sequential Patterns (S2P). We aim at identifying relationships such as: the presence of dengue cases in an area is often preceded by high temperatures and the presence of water tanks in a neighboring area. Thus, we will deal with the developments and interactions between the study area and its immediate environment. Moreover, as this kind of patterns are very difficult to mine, because of the huge generated search space, we will introduce an interestingness measure to make our approach more scalable.

S2P (Spatio-Sequential patterns): Concepts and definitions

In this section, we present the basic concepts around the spatio-sequential patterns.

Preliminaries

A spatiotemporal database is a structured set of information including geographic components (e.g., neighborhoods, rivers, etc.), temporal components (dates) and events (e.g., rain, wind). Such a database

A U T H O R C O P Y

Neighbor(Z i , Z j ) = true, if zones Z i and Z j are nearby Neighbor(Z i , Z j ) = false, otherwise Each dimension D Ai (∀i ∈ [1.
.p]) in the set of analysis dimensions D A is associated with a domain of values denoted by dom(A i ). In these domains, the values can be ordered or not.

To illustrate these definitions, we use a weather database as an example. Table 2, represents weather in three zones on three consecutive days, in which, temperature (Temp), precipitation (Prec), wind speed (Wind) and gusts in Km/h are listed. The three zones are associated by a neighborhood relationship described in Fig. 1.

In Table 2, D T = {Date}, D S = {Zone} and D A = {Temp, Prec, Wind, Gusts}. The domain of the temporal dimension is dom(D T ) = {12/22/13, 12/23/13, 12/24/13} with 12/22/13 < 12/23/13 < 12/24/13. The domain of spatial dimension is dom(D S ) = {Z 1 , Z 2 , Z 3 } with Neighbor(Z 1 , Z 2 ) = true, Neighbor(Z 1 , Z 3 ) = true and Neighbor(Z 2 , Z 3 ) = false. Finally, for the analysis dimensions Temp and Gusts, the domains are dom(Temp) = {T m , T l , T s }2 and dom(Gusts) = {55, 75}, respectively.

Spatio-sequential patterns

Definition 1 (Item and Itemset). Let I be an item, a literal value for the dimension

D Ai , I ∈ dom(D Ai ). An itemset, IS = (I 1 I 2 . . . I n ) with n p, is a non empty set of items such that ∀i, j ∈ [1..n], ∃k, k ∈ [1..p], I i ∈ dom(D Ak ), I j ∈ dom(A DA k ) and k = k .
All items in an itemset are associated with different dimensions. An itemset with k items is called k-itemset.

We define the In relationship between zones and itemsets which describes the occurrence of itemset IS in zone Z at time t in the database DB: In(IS, Z, t) is true if IS is present in DB for zone Z at 2). Now, we define the notion of interaction between two nearby zones.

Definition 2 (Spatial itemset). Let IS i and IS j be two itemsets, we say that IS i and IS j are spatially close iff ∃Z i , Z j ∈ dom(D S ), ∃t ∈ dom(D T ) such that In(IS i , Z i , t) ∧ In(IS j , Z j , t) ∧ Neighbor(Z i , Z j ) is true. A pair of itemsets IS i and IS j that are spatially close, is called a spatial itemset and denoted by

I ST = IS i • IS j .
To facilitate notations, we introduce a n-ary group operator for itemsets to be assigned by the operator • (near), denoted by []. The θ symbol represents the absence of itemsets in a zone. Figure 2 shows the three types of spatial itemsets that we can build with the proposed notations. In Fig. 2, the shaded square represents the studied area, each IS represents an itemset and the dotted lines represent spatial neighborhood.

For instance, the spatial itemset

I ST = (T m • P m W l )
describes that events T m and P m W l occur in neighboring zones at the same time. The spatial itemset I ST = (θ • [T m ; P l ]) indicates that T m and P l occur in two different zones neighbor to a zone where no event appears. Definition 3 (Association between zone, spatial itemset and time). Let I ST = IS i • IS j be a spatial itemset, Z ∈ dom(D S ) be a zone and t ∈ dom(D T ) be a timestamp, we define the relation Verify that represents the occurrence of the spatial itemset I ST in Z at time t as follows: 2).

⎧ ⎪ ⎨ ⎪ ⎩ Verify(I ST , Z, t) = true if In(IS i , Z, t) =

Definition 4 (Inclusion of spatial itemset). A spatial itemset

I ST = IS i • IS j is included in another spatial itemset I ST = IS k • IS l , denoted by I ST ⊆ I ST , iff IS i ⊆ IS k and IS j ⊆ IS l . The spatial itemset I ST = (T l P m •W s ) is included in the spatial itemset I ST = (T l P m •W s 55) because (T l P m ) ⊆ (T l P m ) and (W s ) ⊆ (W s 55).
We now define the notion of zones evolution according to their spatial neighborhood relationship.

Definition 5 (Spatial Sequence). A spatial sequence or simply 2S is an ordered list of spatial itemsets, denoted by s = I ST1 I ST2 . . . I STm where I STi , I STi+1 satisfy the constraint of temporal sequentiality for all i ∈ [1..m -1].

A 2S s = (T l )(θ • [P m ; W s ])(W m • [P l ; T m ]
) is illustrated in Fig. 3 for the zone Z1, where the arrows represent the temporal dynamics and the dotted lines represent the proximity relationship.

A generalization relationship (or specialization) between 2S's is defined as follows:

Definition 6 (Inclusion of 2S

• P l W s )(55) is included in the 2S s = (T l P m • P l W s )(55 • W s ) because (T l P m • P l W s ) ⊆ (T l P m • P l W s ) and (55) ⊆ (55 • W s ).
Definition 7 (Prefix and suffix of 2S). We define the function prefix(S, N ) → S where S is a set of 2S's, N is a set of positive integers, and prefix(s, k) = s [1 : k]. In other words, prefix(s, k) returns the first k items, i.e., the prefix of s. In the same way, we define the function suffix(S, S) → S where S is a set of 2S's. Let s ∈ S with n items and s ∈ S with m items, if s is a prefix of s then the suffix(s, s ) = s[m + 1 : n] returns the 2S of nm last items of the sequence s prefixed by s .

Let the spatial sequence s 1 = (T l P m • P l W s )(55) and s 2 = (T l P m , then, the suffix s 1 compared to prefix s 2 is (_ • P l W s )(55) .

The spatial sequences 2S can be stored in a sequence database seqDB.

Definition 8 (Projection of a sequence database seqDB). Let s be a 2S present in the sequence database seqDB. The s-projected database, denoted by seqDB| s is a set of suffixes of spatial sequences in seqDB prefixed by s.

Pruning measures

In this section, we introduce two pruning measures to filter interesting spatial sequences in the mining process. The first one is an adaptation of the support used in sequential pattern mining [START_REF] Agrawal | Mining sequential patterns[END_REF], while the second one is an adaptation of the cascading participation index used [START_REF] Mohan | Cascading spatio-temporal pattern discovery: A summary of results[END_REF]. To illustrate definitions proposed in this section, we use a database of sequences. The spatiotemporal database presented in Table 2 can be transformed in a database of sequences by organizing the events of the analysis dimension (D A ) by date and by zone. Hence, sequences shown in Table 3 were built from our spatiotemporal database.

Hereafter, each zone Z i ∈ dom(D S ) will be represented by their sequence S i , for example, the sequence S 1 = (T l P m W m )(T m P m W l )(T l P m W m 55) represents the events occurred in Z 1 .

A U T H O R C O P Y

Support of 2S

In sequence mining literature, a common example is the basket data where the database is composed of a set of sequences corresponding to customers transactions. Each transaction consists of customer-id, transaction time and the items bought in the transactions. The absolute support for a sequence is defined as the number of transactions in database which contains the sequence [START_REF] Agrawal | Mining sequential patterns[END_REF]. Our spatiotemporal database is similar to a sequence database, since information of a zone at different times can be viewed as a sequence. The main difference is the neighborhood relationship associated to the spatial dimension. As a consequence, we define a new absolute support for spatial sequences as the number of zones containing the studied sequence that satisfies the proximity constraints of the spatial itemsets. More formally, this measure can be defined as follow: Definition 9 (Absolute support). Let s = I ST1 I ST2 . . . I STn be a 2S, the absolute support of s is defined as:

supp abs (s) = |{Z ∈ dom(D S )|∀i ∈ [1..n], ∃T i ∈ dom(D T ), and V erify(I STi , Z, T i ) = true}| (1)
In the same way, we define the relative support for a 2S as the fraction of total zones which supports a 2S. More formally: Definition 10 (Relative support). Let s = I ST1 I ST2 . . . I STn be a 2S, the relative sequential support of s represented by supp rel (s) or simply supp(s), is defined as:

supp rel (s) = supp(s) = supp abs (s) |dom(D S )| (2)
For instance, consider the neighborhood relationship shown in Fig. 1 and sequences presented in Table 3. Each sequence represents a change in events per zone (see Table 2). Let s = (P m )(T l • T m ) be a 2S, the relative support of s is 2/3 (i.e. s appears in two of three zones). The dynamic and support of s are illustrated in Fig. 4. The arrows represents the temporal changing and dotted lines represents the spatial neighborhood relationship.

Spatiotemporal participation index

The previous support does not take into account the participation of an item in a spatio-sequential pattern. It does not evaluate occurrences of a pattern appearing in the same zone at different times. To highlight these aspects, we propose a new anti-monotonic prune measure called Spatiotemporal Participation Index (STPi). This measure is an adaptation of the cascading participation index [START_REF] Mohan | Cascading spatio-temporal pattern discovery: A summary of results[END_REF] that is a combination of two measures: (1) the spatial participation index, which takes into account the number of zones supporting the pattern, and; (2) the temporal participation index, which takes into account the number of occurrences of a pattern in a zone at different times.

First, we define the spatial participation ratio and the spatial participation index.

Let s be a 2S and I be an item of s. The spatial participation ratio of I in s, denoted by SP r(s, I) is the number of zones which contain s divided by the number of zones where the item I appears in the whole database:

SP r(s, I) = supp abs (s) supp abs (I) (3)
Let s be a 2S, the spatial participation index of s, denoted by SP i(s) is the minimum of spatial participation ratio:

SP i(s) = MIN ∀I∈dom(Ai),I∈s {SP r(s, I)} (4)
Then, we define the temporal participation ratio and the temporal participation index.

Let s be a 2S, let I be an item of s and let S i be a sequence that represents events occurred in Z i which supports s. The temporal participation ratio of I in s denoted by T P r(s, I, S i ) is the number of instances of I participating in an occurrence of s divided by the total number of instances of I in sequence S i supporting s: T P r(s, I, S i ) = nbInstances(I) participating in an occurrence of s nbInstances(I) in S i supporting s (5)

Let s be a 2S, the temporal participation index of s, denoted by T P i(s) is the minimum of temporal participation ratio calculated for each sequence in database:

T P i(s) =MIN Si,i∈dom(DS ) MIN I∈dom(Ai),I∈s {T P r(s, I, S i )}} (6)
Now, using previous definitions, we define the Spatiotemporal Participation Index as follow:

Definition 11 (Spatiotemporal Participation Index). We define the spatiotemporal participation index of a spatial sequence s, ST P i(s), as the product of two measures presented above:

STPi(s) = SP i(s) × T P i(s) (7)
For example, consider the same 2S presented in Section 4.1, i.e., s = (P m )(T l • T m ) . Also, consider the neighborhood relationship shown in Fig. 1 and sequences presented in Table 3, the spatiotemporal participation index for s is 1/3, as shown below: Initially, we compute the spatial participation index: Next, the temporal participation index is computed:

SP i = MIN {SP r(s, P m ), SP r(s, T l ), SP r(s, •T m )} = MIN 2 3 , 2 3 , 2 3 = 2 3 A U T H O R C O P Y
T P i = MIN ∀Si,i∈dom(DS ) {MIN {T P r(s, P m ), T P r(s, T l ), T P r(s, •T m )}} = MIN 2 3 , 1 1 , 2 4 , 1 2 , 1 1 , 1 1 , = MIN 1 2 , 1 2 = 1 2
Finally, two results obtained above are replaced in the equation of spatiotemporal participation index:

STPi(s) = SP i(s) × T P i(s) = 2 3 × 1 2 = 1 3
The main challenge involved in the spatio-sequential patterns mining problem is: let σ be a minimum threshold set by the user, a spatial sequence 2S satisfying STPi(2S) σ is a frequent sequence called Spatio-Sequential Patterns or simply S2P. It is important to notice that we can use the support supp instead of the Spatiotemporal Participation Index STPi to validate a 2S as a frequent sequence.

Discusion

As has been discussed [START_REF] Joshi | A universal formulation of sequential patterns[END_REF], one of the most important task in data mining process is how the frequency of a sequence is estimated. This issue will be addressed in this discussion.

In the literature, there are several measures for evaluating patterns discovered by the data mining process (for an overview, see, e.g., [START_REF] Geng | Interestingness measures for data mining: A survey[END_REF][START_REF] Mcgarry | A survey of interestingness measures for knowledge discovery[END_REF]). For instance, [START_REF] Mohan | Cascading spatio-temporal pattern discovery: A summary of results[END_REF], the authors propose the cascade participation index (CPI), which is defined as the minimum number of instances of an event-type participating in a pattern divided by the number of instances of event-type in all the database. To estimate the CPI, the authors count "globally" the occurrences of a pattern in the whole database.

In this paper, we propose an adaptation of the aforementioned measure taking into account two aspects. First, in TPi, we propose to evaluate the occurrences of a spatial sequence 2S "locally" (as opposed to globally), counting the number of event occurrences in a sequence where the pattern appears (as opposed to whole database). Second, as detailed in [START_REF] Wu | Re-examination of interestingness measures in pattern mining: a unified framework[END_REF], the presence of null-sequences 3 is critically important in the process of computing an interesting measure. Our proposition takes into account this constraint evaluating only the sequences containing the studied spatial sequence 2S.

Extraction of spatio-sequential patterns

In this section, we propose two algorithms associated with the two most common strategies in data mining to find spatio-sequential patterns in a spatiotemporal database. In a first step, we use the breadthfirst search strategy (BFS) and we propose an algorithm BFS-S2PMiner. In a second step, we propose an algorithm DFS-S2PMiner based on a depth-first search strategy (DFS).

(ρX) (ρY ) X < Y (ρXY ) (ρX) (ρ)(Y ) (ρX)(Y ) (ρ)(X) (ρ)(Y ) X < Y (ρ)(XY ) (ρX) (ρ • Y ) (ρX • Y ) (ρX) (ρ)(θ • Y ) (ρX)(θ • Y ) (ρ • X) (ρ)(Y ) (ρ • X)(Y ) (ρ • X) (ρ • Y ) X < Y (ρ • [X; Y ]) (ρ)(θ • X) (ρ)(θ • Y ) X < Y (ρ)(θ • [X; Y ])

Sequences

Neighboring sequences

S1 = (T l PmWm)(TmPmW l )(T l PmWm55) S2 = (TmPmWm)(T l PmW l )(T l P l Wm) S3 = (T l PmWs75)(TmPsW l )(T l PsWs55) S2 = (TmPmWm)(T l PmW l )(T l P l Wm) S1 = (T l PmWm)(TmPmW l )(T l PmWm55) S3 = (T l PmWs75)(TmPsW l )(T l PsWs55) S1 = (T l PmWm)(TmPmW l )(T l PmWm55)

Level-wise approach

In level-wise algorithms (generate-test-prune), the approach first extracts the frequent items, then, for each iteration k, the algorithm generates a set of candidates from frequent patterns generated at iteration k -1. At the end of each iteration, a pruning phase based on an anti-monotone property, is done to limit the number of candidate patterns generated. All candidates are tested and only those which are frequent, are used to generate candidate patterns with k items during the next iteration. The algorithm stops when the set of candidates is empty. There are many algorithms based on this approach, among which we find Apriori [START_REF] Agrawal | Fast algorithms for mining association rules in large databases[END_REF] GSP [START_REF] Srikant | Advances in Database Technology EDBT'96[END_REF] or SPADE [START_REF] Zaki | Spade: An efficient algorithm for mining frequent sequences[END_REF]. We propose in this section, a new algorithm derived from the algorithm SPADE introduced by Zaki [START_REF] Zaki | Spade: An efficient algorithm for mining frequent sequences[END_REF].

Initially, our algorithm extracts frequent items (lines 1 to 8 in Algorithm 1) to construct the set F 1 . From this set F 1 , we construct the candidates of iteration 2. In general, at each level, we construct set of patterns with k + 1 items from those with k items. Note that in each iteration k, the patterns generated have k items. For example, consider two spatial sequences (XY • Z) and (XY )(Y ) , both composed of three items. The prefix of these two patterns is XY then we can generate the pattern (XY • Z)(Y ) with four items.

More formally, let the sequences α and β having the same prefix ρ. In the candidate generation step, we generate candidate patterns γ having the same prefix following the rules described in Table 4.

In the pruning step, the algorithm prunes candidate patterns which have an unfrequent k-1 sub-pattern (line 15). For example, the pattern (XYZ) is not generated if one of its sub-patterns (e.g., (XY) ) is not frequent.

Finally, once the pruning step is complete, the algorithm tests each candidate patterns (line 16) and uses the k-frequent patterns discovered to begin the next iteration. Algorithm 1 is the pseudo-code for this proposal.

We illustrate our proposal using the neighborhood relationship described in Fig. 1, a minimal threshold σ = 2/3 and a sequence database described in Table 5. This table is divided in two parts: the first stores the sequences that represent the evolution over time in each zone of the spatiotemporal database, and, the second one, stores sequences associated to their neighboring zones.

Algorithm 1 BFS-S2PMiner

Require: A sequence database seqDB, a neighborhood relationship L and a minimal threshold σ Ensure: A set of frequent spatio-sequential patterns 1: for all i ⊆ dom(A i ) where i ∈ [1.

.p] do 2:

if ST P i(i) σ then 3:

F 1 ← F 1 ∪ {i} 4:
end if

5:

if ST P i(•i) σ then 6:

F 1 ← F 1 ∪ {•i} 7:
end if 8: end for 9: k ← 1 10: while F k = ∅ do 11:

F k+1 ← ∅ 12: for all α ∈ F k , β ∈ F k do 13: if prefix(α) = prefix(β) then 14: γ ← union(α, β) 15: if AllSubSeqF req(F k , γ) then 16:
if ST P i(γ) > σ then 17:

F k+1 ← F k+1 ∪ {γ}
k ← k + 1 23: end while 24: return F 1 ∪ F 2 ∪ . . . ∪ F k
Lines 1 to 8 of our algorithm calculates the set F 1 of frequent items, by checking that the minimal threshold σ is achieved. F 1 is composed of all items that appear at least twice in sequences associated with zones and those that appear at least twice in their neighboring sequences.

In our example (see Table 5), the item W m appears twice in sequences S 1 and S 2 and item •W m appears three times: in the neighborhood of S 1 (i.e., in S 2 ) in the neighborhood of S 2 (i.e., in S 1 ) and in the neighborhood of S 3 (i.e., in S 1 ). Finally, F 1 is composed of:

F 1 = {T l : 3, W m : 2, W l : 3, P m : 3, T m : 3, 55 : 2, •T l : 3, •W m : 3, •W l : 3, •P m : 3, • T m : 3, •55 : 3}
The number associated with these items is the frequency of occurrence of these items in Table 5. We can notice that item •T l appears four times in neighboring sequences, but its support is three. In fact, item •T l appears once in the neighborhood of S 2 , once in the neighborhood of S 3 and twice in the neighborhood of S 1 . However, in this latter case, the support of •T l is counted only one time because it appears in the same neighboring areas of S 1 .

From the set F 1 , we construct the set F 2 of spatio-sequential patterns prefixed by frequent patterns found in the previous step. In general, we proceed as follows: if two patterns have the same prefix (line 13), we generate a candidate pattern γ with k + 1 items which is obtained by the union of two frequent patterns containing k items according to the cases presented in Table 4 (line 14).

Examples of candidates with 2 items generated from the set F 1 are (T l )(T l ), (T l W m ), (T l W m ), . . ., (T l • T l ), (T l )(θ • T l ), . . . In this set of two candidates, we only keep those whose subsets of size 1 are frequent (line 15). Then, at line 16, the algorithm checks whether the candidate patterns of size 2 are frequent. For example, the pattern (T m )(W f ) is frequent because it appears twice in sequences S 1 and S 2 (see Table 5).

Finally, we obtain the set of frequents spatio-sequential patterns composed of 2 items:

F 2 = {(T l )(T l ) : 3, (T l • T l ) : 3, (T l )(θ • T l ) : 2, (T l W m ) : 2, (W m • W m ) : 3, (P m )(P m ) : 2, (P m • P m ) : 3, (P m )(θ • P m ) : 3, . . .}
By performing previous steps iteratively, the algorithm continues until there is no candidate that can be generated. Then, it returns the set of frequent spatio-sequential patterns.

SPADE is considered as an Apriori-like algorithm. The computation complexity of BFS-S2PMiner is, in the worst-case, O(T N(2M ) N ) where T is the number of transactions on the database (|dom(D S )|), N is the number of different items in the database and M is the maximum number of neighboring zones.

Depth-first approach

In this section, we propose an algorithm called DFS-S2PMiner to extract spatio-sequential patterns considering both spatial and temporal aspects. DFS-S2PMiner adopts a depth-first-search strategy based on successive projections of the database such as FP-Growth [START_REF] Han | Freespan: Frequent pattern-projected sequential pattern mining[END_REF] and Prefixspan [START_REF] Mortazavi-Asl | PrefixSpan: Mining sequential patterns efficiently by prefix-projected pattern growth[END_REF]. Specifically, this algorithm is based on the pattern-growth strategy used [START_REF] Han | Freespan: Frequent pattern-projected sequential pattern mining[END_REF]. The principle of this approach is to extract frequent patterns without a candidate generation step. Indeed, the level-wise algorithm stage can be very expensive due to the large number of candidate patterns that can be generated. Moreover, it requires repeated scanning of the database and checking of the support of a large number of patterns. Strategies such as pattern-growth avoid this by using a divide and conquer approach. This approach recursively creates a projected database (cf. Definition 8), associates it with a fragment of frequent pattern, and "mines" each projected database separately. The frequent patterns are extended progressively along a depth-first exploration of the search space.

The Algorithm 2 describes our recursive algorithm DFS-S2PMiner. First, the set of frequent items I and θ•I, denoted by F 1 , is extracted from the projected database seqDB| α (line 1 of Algorithm 2). These items constitute extensions of the sequence α. Note that in the first recursive call, seqDB| α corresponds to the initial database seqDB (since α = {}). Then, for each of these items X ∈ F 1 , we extend the spatio-sequential pattern α with X (lines 3 and 4). Two types of extension are possible: 1) adding X to the last spatial itemset of the sequence α (line 3) or 2) inserting X after (i.e., the next time) the last spatial itemset of α (line 4). We check the interestingness measure for these two spatio-sequential patterns (lines 5 and 9) and record frequent ones in the set of solutions F (lines 6 and 10). For each frequent pattern, the algorithm then performs another projection of the database using seqDB| α and recursively extends the pattern by invoking again the algorithm (lines 7 and 11). The algorithm stops when no more projections can be generated. We use our running example (Table 5 and Fig. 1) with σ = 2/3 to illustrate this algorithm.

A U T H O R C O P Y

Sequences

Neighboring sequences

S1 = (_Wm)(TmPmW l )(T l PmWm55) S2 = (_Wm)(T l PmW l )(T l P l Wm) S3 = (_Ws75)(TmPsW l )(T l PsWs55) S2 = (_Wm)(T l PmW l )(T l P l Wm) S1 = (_Wm)(TmPmW l )(T l PmWm55) S3 = (_Ws75)(TmPsW l )(T l PsWs55) S1 = (_Wm)(TmPmW l )(T l PmWm55)
Algorithm 2 DFS-S2PMiner -Main routine Require: A sequence database seqDB and a user-defined threshold σ Ensure: A set of frequent spatio-sequential patterns F α ← {} Prefix-growthST(α, σ, seqDB| α , F ) -Prefix-growthST(α, σ, seqDB| α , F )

Require: a spatio-sequential pattern α, the user-defined threshold σ, the projection seqDB| α of the sequence database on α, and F a set of frequent spatiotemporal patterns; 1. F 1 ← {a set of frequents items I and θ • I on seqDB| α , with

I ∈ i∈[1..p] dom(D Ai )} 2. for all X ∈ F 1 do 3. β ← αX 4. δ ← α(X) 5. if ST P i(δ) σ then 6. F ← F ∪ δ 7.
Prefix-growthST(δ, σ, seqDB| δ , F ) 8. end if 9. if ST P i(β) σ then 10.

F ← F ∪ β 11.

Prefix-growthST(β, σ, seqDB| β , F ) 12. end if 13. end for Iteration 1 (α = {})

The first step concerns the extraction of frequent items and frequent spatial items from seqDB (line 1 of Algorithm 2), let:

F 1 = {P m : 3, T m : 3, W m : 2, W l : 3, T l : 3, 55 : 2, θ • T m : 3, θ • P m : 3, θ • W m : 3, θ • W l : 3, θ • T l : 3, θ • 55 : 3}
Next, the current sequence α is extended (lines 3 and 4). Thereafter, in lines 5, 6 and 9, 10, we process the STPi and record the solutions respectively.

For each frequent item I and θ•I, the algorithm calculates the corresponding projection of the database (lines 7 and 11). For example, for the frequent item P m , we obtained the following projection (see Table 6). Each of these projected databases are used in a recursive call to find its frequent super-sequences.

Iteration 2 (α = (P m ) )

A U T H O R C O P Y

H. Alatrista-Salas et al. / Spatio-sequential patterns mining: Beyond the boundaries

Table 7

Projected database of (Pm)(Wm)

Zones Sequences

Neighbors Neighboring sequences

Z1 S1 = (TmPmW l )(T l PmWm55) Z2 S2 = (T l PmW l )(T l PmWm) Z3 S3 = - Z2 S2 = (T l PmW l )(T l P l Wm) Z1 S1 = (TmPmW l )(T l PmWm55) Z3 S3 = ∅ Z1 S1 = (TmPmW l )(T l PmWm55)
The first recursive call will build the super-sequences with the prefix (P m ) from the projected database of Table 6. Specifically, the algorithm will find frequent items in the projected database (line 1) and extend (P m ) (lines 3, 4). The frequent items obtained from seqDB| (Pm) are:

{W m : 2, T m : 2, P m : 2, W l : 3, T l : 3, 55 : 2, θ • W m : 3, θ • T l : 3, θ • P m : 3, θ • W l : 3, θ • T m : 3, θ • 55 : 3}
The first frequent item found is W m : 2. Therefore, we can build two spatial sequences: (P m W m ) (line 3) and (P m )(W m ) (line 4).

In lines 5, 6 and 9, 10, we process the STPi and record the solutions. For instance, the spatio-sequential pattern (P m )(W m ) with ST P i = 2/3 is frequent (line 9).

Later, a projection and a recursive call are performed (lines 7 and 11). Thus, the algorithm uses this pattern to make a new projection (see Table 7) and to recursively search all frequent super-sequences with the prefix (P m )(W m ) .

Iteration 3 (α = (P m )(W m ) )
The frequent items obtained for seqDB| (Pm)(Wm) are:

{W m : 2, P m : 2, W l : 2, T l : 2, θ • W m : 3, θ • T l : 3, θ • P m : 3, θ • W l : 3, θ • 55 : 3}.
Next, we extend the current sequence α (lines 3, 4). For example, the spatial item θ • P m : 3 is one of the frequent items. In this case, the algorithm builds the spatio-sequential pattern (P m )(W m )(θ • P m ) . This pattern is frequent with a ST P i = 1 because θ • P m appears in all times and zones (see Table 7).

Finally, a projection and a recursive call (lines 7 and 11) are performed. When all frequent items are projected, the algorithm goes through another branch of the search space, i.e., patterns beginning with (T m ) (see set F 1 ).

The algorithm thus proceeds generally in the same way whether items are spatial or not. The main difference is how to identify a frequent sequence. The support of a spatial item is the number of zones where the item occurs at least once in their neighborhood (so we have θ • W l : 3 in Table 6). Notice that when the algorithm extends a pattern of type (I ST1 )(I ST2 ) . . . (I STk • X) with a common item θ • Y , the operator of n-ary group is used to represent the sequence as

(I ST1 )(I ST2 ) . . . (I STk • [X; Y ]) .
The worst-case computation complexity of DFS-S2PMiner is O((2NM) L ) where N is the number of different items in the database, M is the maximum number of neighboring zones, and L is the maximum length of all transactions. The constant 2 is introduced since each item can be added into transaction through either itemset or sequence extension.

Experiments and results

In order to evaluate the performance of our propositions, experiments were performed on two real spatiotemporal datasets with different relevant feature types (e.g., number of dengue cases, river pollution measure. . . ) and also on synthetic datasets generated using empirical realistic values. In the early part of this section, we will describe the datasets, later, we analyze our results taking into account qualitative and quantitative aspects. This section ends with a performance and scalability study.

A U T H O R C O P Y

Dataset description

Proposed algorithms were tested using synthetic and real datasets described below.

Synthetic datasets

To obtain randomly generated data, we construct a configurable synthetic data generator with the following parameters: number of zones, type of neighborhood relationships, number of dates per zone and the average number of items per zone. This generator allows us to build two types of neighborhood relationships (see Fig. 5). The first one is used to represent the space as a grid where each square represents an area. An area will have eight neighbors. The second one is used to represent the space as a graph structure where vertices represent zones and edges represent neighborhood relationships. In the last case, the generator takes as input parameters the number of edges and the number of vertices. Large and different synthetic datasets were generated to evaluate our algorithms. Simulation parameters were chosen based on empirical realistic values.

As a summary, Table 8 shows the characteristics of the synthetic datasets that have been used for experimentations.

Dengue dataset

Dengue is a mosquito-borne infection (Aedes aegypti) that occurs in all tropical and subtropical regions of the planet. Currently, dengue viral infection has become an increasing global health concern with over two-fifths of the world's population at risk of infection. It is the most rapidly spreading vector borne disease, attributed to demographics, urbanization and environment changing. The severe dengue (formerly known as dengue hemorrhagic fever) was first identified in the fifties of last century during an outbreak in the Philippines and Thailand. Today, this disease affects most of the countries in Asia and Latin America (over 100 tropical and sub-tropical countries) and has become one of the leading causes of hospitalization and death among children in these regions. An estimated 500 000 people with severe dengue require hospitalization each year, a large proportion of whom are children. About 2.5% of those affected die. 4 In the context of a collaboration between the University of New Caledonia, the Department of Health and Social Affairs of New Caledonia, the Pasteur Institute and the Institute of Research for Development, we have analyzed data associated with epidemiological monitoring of dengue. These data were collected in Nouméa (New Caledonia) in a territory divided into 81 zones covering 45.7 km 2 . This spatial division was proposed by the Direction of Health and Social Affairs in New Caledonia. This dataset contains information associated to: population data, entomological data, meteorological data, urban planning data and medical data which are summarized in Table 9. Overall, the dengue dataset contains between 22 dates in average by zone and in average 22 items by date.

Population data: population data is related to population census and includes the code of zone, the number of inhabitant, the number of houses, the number of households, etc. This data was collected during two epidemic years (1996 and 2003) for each zone in Nouméa.

Entomological data: this data is associated to the characteristics of transmission vector (Aedes aegypti). This data includes Breteau Index (IB), Entomological High Risk Index (IHRE), data related to serotype, the positivity rate and other information used by the epidemiologists to analyze the disease. In this category, the data is retrieved by zone and the time granularity is monthly.

Meteorological data: this data comprises several weather signs such as precipitations (mm), wind strength (m/s), temperature (°C) and humidity (%). This data was recorded daily for each zone in Nouméa.

Urban planning data: Aedes aegypti mosquitoes live and breed in urban areas in close proximity to humans. The mosquito breeds in artificial containers (e.g., old tires, pot plant trays, urns or rainwater containers) that collect water and feeds almost exclusively on human blood. Considering these two aspects, we integrate: (1) in one hand, data associated to essential breeding ground for mosquitoes development as number of pools, number of greenhouses, number of basins or watersheds, fountains, and; (2) data related to places where people gather for social activities like, schools, churches, nurseries, etc.

Medical data: this data only comprises the number of dengue cases reported in Nouméa per day. Years 1996 and 2003 are the most important in terms of number of dengue cases. We will use only the data of 2003 which contains dengue cases.

In order to obtain categorical data (data separable into categories that are mutually exclusive), a discretization has been done to recode continuous data into categorical data by using the discretization method of equi-width binning. The data is stored according to three range of values within which they are classified: low, medium and high.

Saône watershed dataset

Rapid population growth and human activities development (such as agriculture, industry, transports. . . ) have increased vulnerability risk for water resources. In this context, river pollution is a phenomenon which is observed by measuring physicochemical and biological indicators for water quality. These indicators which evolve over time, depend explicitly on the location of sampling stations strategically located along several rivers.

The monitoring of stations placed along the Saône watershed produces several hydrological data. This data has been supplied by the RMC water agency5 in the context of the Fresqueau project. 6 This project aims to develop new data mining techniques related to the water data management.

The data at our disposal is geo-referenced and temporally variable, thus making it difficult to explore globally. Moreover, the spatial relationship between the studied objects (i.e., monitoring stations) is implicit. It is therefore necessary to perform pre-processing that takes into account different spatial proximities (e.g., grouping stations according to their distance, according to their association to the same zone. . . ) in order to build homogeneous zones and determine their neighboring areas.

In this work, our proposal consist on pre-processing data to bring together some monitoring stations and building homogeneous zones of spatial objects. For this purpose, the space is divided into areas grouping stations by exploiting their Lambert coordinates. In each of these zones, stations that are located within an area of size centered on station X are grouped, even if these stations belong to different watercourses. As can be clearly seen in Fig. 6, stations X and Y are considered to be in the same area, even if they are not on the same watercourse. For example, pesticide used in a crop field located between stations X and Y can impact on monitoring stations measures located on rivers around this crop field even if stations are not positioned in the same river. In our experimentations, value was set to 10 km.

Concerning the data itself, two types of data are available: information related to the monitoring station and information which corresponds to data measured by the station. Table 10 shows the attributes for Saône river dataset. Monitoring station information: each station is characterized by an identifier (id) and its spatial coordinates (x, y). The Lambert Projection System 93 is used for the geo-referencing. A kilometric point is also provided and corresponds to the distance from the downstream confluence to the monitoring station following watercourse.

Monitoring station measurements: the stations measure biological indicators that determine the water quality of rivers. The frequency of these records varies with time and stations. Some stations have recurrent sample data while other stations only have a single sample data (e.g., for general monitoring). The main items associated with records are: (1) Standardized Global Biological Index (IBGN), a standardized measure based on identification of macro-invertebrates in rivers, and; (2) Biological Diatom Index (IBD), a standardized measure to diagnostic trophic pollutions (for more information, see e.g., [START_REF] Lafont | A conceptual approach to the biomonitoring of freshwater: The ecological ambience system[END_REF]).

The IBGN and IBD measures have been processed based on: a note (e.g., ibd_note) and the current status of water quality (e.g., ibgn_stat). In addition, three other variables have been included in our dataset: (1) the taxonomic variety (var_taxo) representing the total number of taxa collected during a sampling, even if they are only represented by a single individual; (2) the faunal group that is the more sensitive to pollution (gr_indic), and; (3) the IBD measure established before the DCE regulation in France (ibd2007). All these information is used to estimate the condition of the watercourse at a specific survey point. Overall, the Saône dataset contains, in average, 17 dates by zone and 5 items by time.

More details of the characteristics of the real datasets are given in Table 11.

Experimental protocol

In this section, we focus on the performance evaluation of our proposals w.r.t. five questions:

1. Which one of the two proposed algorithms is the more efficient? 2. What is the impact of neighborhood relationship topology on the S2P extraction process? 3. What is the impact of the number of zones and the number of dates by sequence on the extraction process? 4. Is the spatiotemporal participation index an effective pruning measure? 5. What is the impact of data density on the S2P extraction process? To answer the first question, we apply both approaches (pattern growth and Apriori based algorithms) on synthetic datasets containing 10 zones, 70 dates and 5 items.

To answer the second question, we study the impact of neighborhood topologies using two synthetic datasets containing 10 zones, 50 dates and 5 items in average using both type of neighborhood: (1) the graph neighborhood relationship and; (2) the grid neighborhood relationship (cf. Section 6.1.1).

To answer the third question, we also study the impact of the number of zones on the extraction process. For this, we vary the number of zones (10 and 20 zones by dataset) and we apply DFS-S2PMiner algorithm on these datasets. The impact of the number of dates per sequence on the extraction process also has been studied varying the number of dates per sequence (50 and 70 dates) on synthetic data.

Finally, to answer the two last questions, we have used two geo-referenced real datasets to evaluate the efficiency of the pruning measure and to evaluate the global performance (qualitatively and quantitatively) of our approaches. The two proposed algorithms were developed in Java. The experimentations have been performed on a PC based on Intel (R) Xeon (R) with 16 GB of RAM with Ubuntu Server 9.10 as operating system. The results are discussed in next section.

A U T H O R C O P Y

Results

In this section, we present a qualitative evaluation by giving some examples of extracted spatiosequential patterns and comparing these patterns with other patterns found by the algorithm proposed by Tsoukatos et al. [START_REF] Tsoukatos | Efficient mining of spatiotemporal patterns[END_REF]. Then, we present a quantitative evaluation to estimate the performance of our approaches.

Qualitative results

Tables 12 and13 show spatial sequential patterns extracted during the execution of our algorithm applied to the dengue monitoring and Saône river databases respectively, using a minimum threshold of 0.6 and 0.1 respectively.

Considering the patterns obtained from dengue monitoring data set (see Table 12), we can see that they take into account the neighboring environment. For example, the second pattern in Table 12 can be interpreted by: at time t 0 we found a low presence of precipitations and house water deposits in two different neighboring areas, after, in studied area, we discover some cases of dengue, later, we detect the development of mosquitoes nest in a third neighboring area.

The results obtained in [START_REF] Tsoukatos | Efficient mining of spatiotemporal patterns[END_REF] do not contain this kinds of patterns. As we described in the related work, Tsoukatos et al. are looking for a sequence of events that occur frequently in a spatiotemporal database, without considering a dynamic neighborhood as we have shown in our examples (see Tables 12 and13). Furthermore, quantitatively, our approach and Tsoukatos approach are not comparable due to the difference between the search space generated for both algorithms.

Quantitative results

To evaluate which of the two approaches (depth-first-search or level-wise) is more efficient, we apply both algorithms on synthetic datasets using graph neighborhood relationship (Graph20x70). shows the runtime and the allocated memory for different thresholds. We can observe that the algorithm based on a depth-first-search approach is more efficient with respect to running time and memory use. This conclusion is endorsed by many works in the literature (see, e.g., [START_REF] Chand | Sequential pattern mining: Survey and current research challenges[END_REF]).

As detailed in Section 6.2, we study the impact of the neighborhood relationship topology on S2P extraction process for different thresholds using two synthetic dataset: Graph20x100 and Grid20x100. Figures 8(a) and (b) show the impact of both types of neighborhood relationship (grid based and graph based) on the execution time and the allocated memory respectively. In these figures, we observe that the execution time increases rapidly for the dataset generated using the grid based neighborhood relationship (8 neighbors by zone). In contrast, using the second neighborhood relationship, we get better results. These results show that the neighborhood relationship has an important impact in the extraction process, particularly on memory occupancy.

Thereafter, we want to estimate the impact of the number of zones and times per sequence on the pattern growth algorithm. Figure 9 shows the impact of zones and dates variation on the S2P extraction process respectively using four datasets: Graph10x70, Graph20x70, Graph10x50 and Graph10x70. It is clear that, for dataset containing 20 zones and 70 dates per sequence, the execution time and the memory occupancy is higher. We can also notice that, an increase of the number of dates increases the computational resources more than an increase of the number of zones. Finally, we evaluate the effectiveness of the spatiotemporal participation index (STPi) measure proposed in Section 4.2 and we show the global results. Purposely, we apply DFS-S2PMiner algorithm on two real datasets. In Fig. 10, the number of patterns extracted using the STPi measure is lower than the number of patterns extracted using the classical support. These results show that the STPi is very restrictive due to the temporal participation index (TPi). Indeed, this support filters the results by keeping only the patterns that appear several times in the spatiotemporal database. We see this phenomenon in the dengue datasets and more clearly on the river datasets (see Fig. 10). The results show the ease Fig. 10. Evaluation of STPi measure effectiveness using Saône river and dengue datasets respectively on (a) runtime (b) memory (c) number of S2P extracted. (Colours are visible in the online version of the article; http://dx.doi.org/10.3233/IDA-160806) of mining the watershed Saône dataset due to the time granularity and consequently the low density of data. For this dataset the extraction processes begins with a minimal threshold of 0.5 and we obtain good performances even using a low threshold.

A U T H O R C O P Y

We can notice that, for dense datasets (e.g., dengue monitoring dataset), the execution time and the memory occupancy is higher. In contrast, for datasets containing a significant number of null values, the execution time and the memory occupancy of S2P extraction process is lower (e.g., Saône river dataset).

DFS-S2PMiner algorithm has a good performance in datasets containing short sequences (e.g., Saône river dataset). Unfortunately, when mining long sequences (i.e., dense datasets) or when using very low threshold, the performance of our algorithm degrades dramatically. Despite the reduced number of extracted patterns, the runtime and the allocated memory for STPi and Support remains the same for higher thresholds but differs for lower thresholds. This result can be explained by the fact that the process of computing the STPi measure increases the overall complexity of the extraction process. We have computed the mean square error between curves in Fig. 10(a) and (b) on the left side. These values are 172.15 sec. and 86265.5 kB, respectively for runtime and memory occupancy for dengue dataset.

Finally, the algorithm based on the depth-first-search strategy is more efficient that the algorithm based on the Apriori approach. This difference is due to the expensive candidate sequences generation used by the level-wise algorithms.

Conclusion and perspectives

In this paper, we propose a new concept of spatiotemporal patterns called spatio-sequential patterns (S2P). This new type of patterns is used to analyze changes in a zone over time taking into account the neighboring environment. This concept describes, for example, the spatial and temporal evolution of dengue depending on the characteristics of zones (quarters) and their neighborhood. A formal framework is established to define the S2P generically.

To extract these patterns, we propose two generic algorithms called DFS-S2PMiner based on a depthfirst strategy and BFS-S2PMiner based on a level-wise approach. We also proposed two interestingness measures which take into account spatial and temporal aspects. We tested our algorithm and the two defined measures on five synthetic datasets and two real datasets.

Among possible future developments of our work, we first try to mine only a compact set of spatiotemporal patterns using, for instance, the notion of top-k patterns or maximal patterns. Later, we want to filter the interesting patterns integrating a declarative patterns mining approach for spatiotemporal databases or integrating constraints in the patterns mining process. Moreover, it is important to analyze the patterns and to provide a visualization tool to help decision makers.

Fig. 2 .

 2 Fig. 2. Graphical representation of spatial itemsets (a) IS1 • IS2 (b) θ • IS2 (c) IS1 • [IS2; IS3]. time t. In our example, consider the itemset IS = (T m P m W l ) then In(IS, Z 1 , 12/23/13) is true as the itemset (T m P m W l ) occurs for zone Z 1 on 12/23/13 (see Table2). Now, we define the notion of interaction between two nearby zones.

  true, and ∃Z ∈ dom(D S ) such that Neighbor(Z, Z ) = true and In(IS j , Z , t) = true Verify(I ST , Z, t) = f alse, otherwise Consider the spatial itemset I ST = (P m W m • 75) then Verify(I ST , Z 1 , 22/12/2013) = true indicates that itemset (P m W m ) occurs in zone Z 1 and (75) in a neighbor of Z 1 at time 12/22/2013 (see Table

Fig. 3 .

 3 Fig. 3. Spatiotemporal dynamic of sequence (T l )(θ • [Pm; Ws])(Wm • [P l ; Tm]) that describes the evolution of the zone Z1. (Colours are visible in the online version of the article; http://dx.doi.org/10.3233/IDA-160806)

Fig. 5 .

 5 Fig. 5. Types of neighborhood relationships (a) grid type (b) graph type.

Figure 7 AFig. 8 .

 78 Fig. 8. Evaluating the impact of different neighborhood relationship topology considering (a) runtime (b) memory. (Colours are visible in the online version of the article; http://dx.doi.org/10.3233/IDA-160806)

Fig. 9 .

 9 Fig. 9. Evaluating the impact of the variation of the number of zones and the number of dates on synthetic dataset considering (a) runtime (b) memory (c) number of S2P extracted. (Colours are visible in the online version of the article; http://dx.doi.org/ 10.3233/IDA-160806)

Table 1

 1

		Summarization of related work
	Reference Pattern type	Spatiotemporal properties	Interesting measure

Table 2

 2 Weather changes in three zones: Z1, Z2 and Z3 on December 22, 23, 24, 2013 defined as a triplet DB = (D T , D S , D A ) where D T is the temporal dimension, D S the spatial dimension and D A = {D A1 , D A2 , . . . , D Ap } a set of analysis dimensions associated with attributes. The temporal dimension is associated with a domain of values denoted by dom(D T ) = {T 1 , T 2 , . . . , T

	Zone	Date	Temp	Prec	Wind	Gusts
	Z1	12/22/13	T l	Pm	Wm	-
	Z1	12/23/13	Tm	Pm	W l	-
	Z1	12/24/13	T l	Pm	Wm	55
	Z2	12/22/13	Tm	Pm	Wm	-
	Z2	12/23/13	T l	Pm	W l	-
	Z2	12/24/13	T l	P l	Wm	-
	Z3	12/22/13	T l	Pm	Ws	75
	Z3	12/23/13	Tm	Ps	W l	-	Fig. 1. Neighboring zones.
	Z3	12/24/13	Tm	Ps	Ws	55

is t } where ∀i ∈ [1..t], T i is a timestamp and T 1 < T 2 < . . . < T t . The spatial dimension is associated with a domain of values denoted by dom(D S ) = {Z 1 , Z 2 , . . . Z l } where ∀i ∈ [1..l], Z i is a zone. We define a neighborhood relationship on dom(D S ), which is denoted by Neighbor, as:

  ). A 2S represented by s = I ST1 I ST2 . . . I STm is more specific than a 2S s = I ST1 I ST2 . . . I STn , denoted by s s , if there exists j 1

			. . .	j m such that I ST1 ⊆
	I STj 1	, I ST2 ⊆ I STj 2	, . . . , I STm ⊆ I STj m .
	A 2S s = (T l P m

Table 3

 3

		Sequences per zone
	Zone Sequences
	Z1	S1 = (T l PmWm)(TmPmW l )(T l PmWm55)
	Z2	S2 = (TmPmWm)(T l PmW l )(T l P l Wm)
	Z3	S3 = (T l PmWs75)(TmPsW l )(TmPsWs55)
	Fig. 4. Spatiotemporal dynamic of S2P (Pm)(T l • Tm) , that appears twice: in Z2 and in Z1. (Colours are visible in the online
	version of the article; http://dx.doi.org/10.3233/IDA-160806)

Table 4

 4

		Generation of candidate patterns
	Sequence α	Sequence β	If	Candidate pattern γ

Table 5

 5 Multi-sets of sequences and neighboring sequences

Table 9

 9 Attributes of dengue monitoring dataset

	Attribute	Description
	id_zone	Zone identification
	Date	Record date
	Precip	Precipitation in mm by comune
	mean_wind	Mean wind strength in m/s by zone
	mean_temper	Mean temperature in °C by zone
	mean_humid	Mean humidity in % by zone
	outdoor_deposit	Number of water deposits in outdoor communal areas (ponds, watersheds, fountains, etc.)
	Graveyard	Number of cemeteries by zone
	waste_container	Waste containers by zone
	indoor_deposit	Number of water deposit in urban areas (drainage, ditches, outlets, standpipe inlets, etc.)
	community_gather Number of communal centers resembling people (schools, churches, universities, etc.)
	ihre_index	Entomological high risk index
	nb_cas_dengue	Number of dengue cases by zone

Table 10

 10

		Attributes of Saône river dataset
	Attribute	Description
	id_area	Zone identification
	date	Date
	ibgn	Standardized global biological index
	gr_indic	The faunal group
	var_taxo	Taxonomical variable
	ibgn_etat	Biological state associated with IBGN
	ibgn_note A note for IBGN
	ibd	Biological diatom index
	ibd2007	IBD measure before 2007
	ibd_etat	Biological state associated with IBD
	ibd_note	A note for IBD
	ibd_ibgn	Pondered value including IDB and
		IBGN measures
		Fig. 6. Construction of zones using Lambert coordinates.

(Colours are visible in the online version of the article; http://dx. doi.org/10.3233/IDA-160806)

Table 11

 11

			Characteristics of real datasets
	Dataset Number	Number of dates	Number of items	Time	Spatial
		of zones by zone (average) by date (average) granularity granularity
	Dengue	12	23	22	Weekly	Quarters
	Saône	223	17	5	Daily	100 km 2

Table 12

 12

			Table 13
	Examples of spatio-sequential patterns extracted from dengue mon-	Examples of spatio-sequential patterns extracted from
	itoring database		Saône river database
	Frequent spatio-sequential patterns	STPi	Frequent spatio-sequential patterns	STPi
	(mean_wind:<=3.20 mean_temper:<=23.55)		(var_taxo_31-40)
	(θ•[waste_container:<=39.00;		(θ•[ibgn_16-20; ibgn_etat_very_good]) 0.32
	comunity_gather:<=20.00;		(ibgn_11-15)
	nb_cas_dengue:<=6.00;		(θ•ibgn_etat_very_good)
	ihre_index:<=24.55])	0.70	(θ•var_taxo_31-40)	0.29
	(ihre_index:>34.82 nb_cas_dengue:<=6.00)	0.60	(var_taxo_21-30)
	(θ•[precip:<=0.10; indoor_deposit:(2126.00;2692.50]]		(θ•[ibgn_11-15; var_taxo_21-30;
	(nb_cas_dengue:<=6.00)		ibgn_etat_mean])	0.25
	(θ•ihre_index:<=24.55)	0.60	. . .
	(θ•ihre_index:>34.82)
	(nb_cas_dengue:<=6.00 mean_temper:<=23.55)
	(θ•comunity_gather:<=20.00)
	(θ•[nb_cas_dengue:<=6.00; ihre_index:<=24.55]) 0.60
	. . .

s = strong, m = medium, l = low. A U T H O R C O P Y

A null-sequence w.r.t. an item I, where I ∈ dom(Ai), is a sequence in a sequence database that does not contain the item I.

Official website of World Health Organization.

http://www.eaurmc.fr/.

http://engees-fresqueau.unistra.fr/.


VACUUM BAKING AT LOW TEMPERATURE AS AN ALTERNATIVE TO REDUCE ENERGY CONSUMPTION OF BREAD BAKING PROCESS The bread baking numerical model A 1D multiphysic model was developped by Doursat et al. [1] (Matlab, Matworks , USA) and validated on experimental data (water loss, CO2 release [2], local porosity [3], global expansion, water content profiles)

■ Energy was transported by conduction, convection and also by evaporationcondensation-diffusion ■ Air, CO 2

Numerical vacuum baking simulations

Four baking simulations were carried out (baking time; 25 min). The baking occurred first at the atmospheric pressure, at 185°C without crust restriction (Fig. 1 a) and with crust restriction (Fig. 1 b). Then, the external pressure was smoothly numerically reduced down to -20 kPa without crust restriction (Fig. 1 c) and with crust restriction (Fig. 1 d). Crust restriction was simulated by setting a maximal height in the model. The impact of the crust setting on the crumb density (the white isolines in the figures) could be so evaluated.

Gas generation and dough mechanical resistance inside bread drive the bubble growth during bread making. The objective was to evaluate the impact of a lowering of external pressure on bread expansion during baking. It was evaluated by numerical vacuum baking simulations and MRI experiments.

Contacts :

David Grenier; david.grenier@irstea.fr Tiphaine Lucas; tiphaine.lucas@irstea.fr Christophe Doursat; christophe.doursat@agroparistech.fr

Bread baked in conventional oven

Results

Baking simulation at atmospheric pressure without early crust setting (appropriate surface hydration) (Fig. 1 a) resulted in a quite homogeneous crumb density with a maximum of 250 kg.m -3 . That maximum was reduced down to 200 kg.m -3 when -20 kPa was applied (Fig. 1 c). However the inner densification of the region located between the core and the surface (the black region in Fig. 1 b andd) due to crust setting [4] increased the density from 350 up to 400 kg.m -3 when vacuum was applied (Fig. 1 d). This high densification phenomenon during vacuum baking due to the drying of the surface [5] was confirmed by MRI observations. While at the very beginning of baking, the decrease in the external pressure reduced the crumb density (the blue region in Fig. 2 b compared to the green one in Fig. 2 a), the high drying rate due to vacuum caused early crust restriction and dough heterogeneity (Fig. 2 d). Indeed, when energy transfer at the bottom was increased (Fig. 2 d compared to c) the green region extended and the overall expansion was reduced at the end.

The Magnetic Resonance Imager

Conclusion

Numerical simulations were first used to identify the extent of the lowering in crumb density that could be expected with the moderate vacuum baking technology. Then MRI observations made it possible to dynamically check the way crust restriction limited the expansion and increased dough density heterogenity. At the end, vacuum baking was found to be a way for managing the crumb density during baking provided that the setting of the crust could be delayed [6].

  viscosity (450 Pa.s) up to the crumb viscosity (4.5x10 6 Pa.s) at Ts = 65°C

Fig. 2 .

 2 Fig.2. MRI images after image processing. The blue areas are less dense than the green areas. a) Image of the central slice of a 70 g roll just before -20 kPa vacuum was applied b) The same roll just after -20 kPa vacuum was applied c) Images of the central slice during baking at 130°C inside the MRI vacuum oven with a plate temperature varying from 30 to 130°C d) Images of the central slice during baking at 130°C inside the MRI vacuum oven with aplate temperature varying from 100 to 130°C

Fig. 1 .

 1 Fig. 1. 1D simulation of bread baking. The white isolines are the isodensity lines (in kg.m -3 ) . The black isolines are at the same temperature (To is the dough opening temperature, Ts is the stiffening temperature; the boiling temperature is presented too) . The gray colors present the instantaneous change in porosity. The scale is presented in the colorbar on the right hand side. a) Baking at amospheric pressure without crust setting b) Baking at amospheric pressure with crust setting c) Baking at -20 kPa without crust setting d) Baking at -20 kPa with crust setting

irstea, Food Process Engineering Research Unit, 17 avenue de Cucillé, CS 64427, 35044 Rennes cedex, France (david.grenier@irstea.fr)

Université européenne de Bretagne, F-35000 Rennes, France

AGROPARISTECH, Joint Research Unit Food Process Engineering, Massy, France

Acknowledgement

This study has been carried out with financial support from irstea and Région de Bretagne.