Manuel Berg

Jérôme Atencia

Line Van Den Berg
email: line.van-den-berg@inria.fr

Manuel Atencia
email: manuel.atencia@inria.fr

Jérôme Euzenat
email: jerome.euzenat@inria.fr

Agent Ontology Alignment Repair through Dynamic Epistemic Logic

Keywords: Ontology alignment, alignment repair, agent communication, dynamic epistemic logic

HAL is

INTRODUCTION

Agents use ontologies to represent their knowledge of the world. Generally, these ontologies are not the same. This causes a problem when agents try to communicate: how do the agents understand each other if they express their knowledge in different ways? This question is part of the more general problem of facilitating interoperability between agents while preserving heterogeneity in their information. Ontology matching algorithms have been developed to allow agents with different knowledge representations, structured in ontologies, to communicate [START_REF] Shvaiko | Ontology Matching: State of the Art and Future Challenges[END_REF]. These aim to find relationships holding across entities of two ontologies, the ontology alignment.

Alignments are typically computed and provided as input to the agents before any communication or joint task occurs.

Ontology matching algorithms may output only partially correct or incomplete alignments. This means that, even if alignments are available, communication failures can still occur due to mistakes in the alignment. There have been several attempts to repair ontology alignments [START_REF] Aberer | Start making sense: The Chatty Web approach for global semantic agreements[END_REF][START_REF] Jiménez-Ruiz | Limiting Logical Violations in Ontology Alignnment Through Negotiation[END_REF][START_REF] Santos | Ontology alignment repair through modularization and confidence-based heuristics[END_REF] that have been integrated with multi-agent systems via specific protocols [START_REF] Aberer | Start making sense: The Chatty Web approach for global semantic agreements[END_REF][START_REF] Payne | Negotiating over ontological correspondences with asymmetric and incomplete knowledge[END_REF]. In these approaches, alignment repair is performed statically, i.e. independently of agent interaction. However, in some multi-agent scenarios, it is not realistic nor desirable for agents to stop interacting until the repair is completed. This is why several approaches to ontology matching have been proposed that attempt to dynamically repair alignments [START_REF] Atencia | An interaction-based approach to semantic alignment[END_REF][START_REF] Chocron | Attuning Ontology Alignments to Semantically Heterogeneous Multi-Agent Interactions[END_REF][START_REF] Chocron | Vocabulary Alignment in Openly Specified Interactions[END_REF]. The Alignment Repair Game (ARG) [START_REF] Euzenat | First Experiments in Cultural Alignment Repair (Extended Version)[END_REF][START_REF] Euzenat | Crafting Ontology Alignments from Scratch Through Agent Communication[END_REF][START_REF] Euzenat | Interaction-based ontology alignment repair with expansion and relaxation[END_REF] that is inspired by ideas of cultural language evolution [START_REF] Steels | Experiments in cultural language evolution[END_REF] is one of them. In ARG, the agents are adaptive: they communicate and, in parallel, evolve alignments through local corrective actions whenever communication fails. This is achieved via adaptation operators that specify precisely how agents adapt the failing correspondence of the alignment.

ARG was evaluated experimentally and the experiments showed that the adaptive agents converge towards successful communication and improve their alignment [START_REF] Euzenat | First Experiments in Cultural Alignment Repair (Extended Version)[END_REF][START_REF] Euzenat | Interaction-based ontology alignment repair with expansion and relaxation[END_REF]. However, experiments alone are not sufficient to logically assess properties of operators; whether they are correct, complete or redundant. In this paper we introduce a formal framework based on Dynamic Epistemic Logic [START_REF] Van Ditmarsch | Dynamic epistemic logic[END_REF] to answer this question. This contributes to (1) providing a formal framework for knowledge and belief evolution for logical agents in ARG, [START_REF] Atencia | An interaction-based approach to semantic alignment[END_REF] formally defining correctness, redundancy and completeness of the adaptation operators, (3) theoretically comparing adaptive agents and logical agents and (4) defining new adaptation operators.

Yet, the scope of this theoretical framework is not limited to ARG: it can be extended to establish formal properties of other games that are designed for agents to improve and repair alignments through interaction. This would allow for a theoretical comparison of different dynamic matching algorithms.

In the remainder, we discuss the related work ( §2) and provide the preliminaries ( §3). We introduce DEOL ( §4) and translate states of ARG to DEOL models ( §5). The formal properties of the adaptation operators are then proved ( §6). We conclude by emphasizing the contribution to the broader dynamic ontology matching field ( §7). violations to agents' ontologies via conservativity principles [START_REF] Jiménez-Ruiz | Limiting Logical Violations in Ontology Alignnment Through Negotiation[END_REF]. These have been integrated with multi-agent systems via specific protocols [START_REF] Aberer | Start making sense: The Chatty Web approach for global semantic agreements[END_REF][START_REF] Payne | Negotiating over ontological correspondences with asymmetric and incomplete knowledge[END_REF]. However, they are performed independently of agent tasks.

To overcome this problem, interaction-situated semantic alignment was proposed [START_REF] Atencia | An interaction-based approach to semantic alignment[END_REF]. This is an ontology matching algorithm as framed by the interaction protocols used by agents to communicate. Alignments are induced depending on repeated successful interactions and failing interactions lead to revision. This proposal was further advanced to repair alignments through their use and generalized to less constrained protocols [START_REF] Chocron | Attuning Ontology Alignments to Semantically Heterogeneous Multi-Agent Interactions[END_REF][START_REF] Chocron | Vocabulary Alignment in Openly Specified Interactions[END_REF].

The Alignment Repair Game (ARG) [START_REF] Euzenat | First Experiments in Cultural Alignment Repair (Extended Version)[END_REF] is inspired by cultural language evolution [START_REF] Steels | Experiments in cultural language evolution[END_REF] to repair alignments through their use. Cultural language evolution offers an experimental methodology in which language (or more generally: culture) is shared amongst a population of agents and evolves through local corrective actions whenever communication fails. ARG adapts this methodology to the evolution of ontology alignments and experiments showed that the adaptive agents converge towards successful communication through local corrective actions [START_REF] Euzenat | First Experiments in Cultural Alignment Repair (Extended Version)[END_REF][START_REF] Euzenat | Interaction-based ontology alignment repair with expansion and relaxation[END_REF].

The purpose of this paper is to examine the corrective actions performed by adaptive agents in ARG from a logical perspective. We introduce a formal framework based on Dynamic Epistemic Logic (DEL) to compare adaptive agents to logical agents, and we prove the logical limitations of the adaptation operators proposed in [START_REF] Euzenat | First Experiments in Cultural Alignment Repair (Extended Version)[END_REF][START_REF] Euzenat | Interaction-based ontology alignment repair with expansion and relaxation[END_REF]. The logic introduced here is an extension of the work on Epistemic Description Logics [START_REF] Baader | Extensions to Description Logics[END_REF]. DEL has been widely used as a framework to reason about information flow in multi-agents systems and has been applied communication [START_REF] Van Benthem | Logics of communication and change[END_REF][START_REF] Van Ditmarsch | Dynamic epistemic logic[END_REF], belief revision [START_REF] Van Benthem | Dynamic logic for belief revision[END_REF] and agent interaction [START_REF] Van Benthem | Logical dynamics of information and interaction[END_REF].

PRELIMINARIES

In this section, we first explain what are ontologies and ontology alignments ( §3.1), then we describe the Alignment Repair Game as a way for agents to evolve alignments ( §3.2) and give the syntax and semantics of Dynamic Epistemic Logic (DEL) ( §3.3). This logic is the basis for the logic introduced later in this paper.

Ontologies and ontology alignments

An ontology provides a vocabulary of a domain of interest and a specification of the meaning of terms via semantic relations: specialization (Ď), equivalence ("), exclusion (') and membership (P) [START_REF] Euzenat | Ontology Matching[END_REF]. Formally, an ontology can be expressed as a knowledge base in Description Logics [START_REF]The Description Logic Handbook: Theory, Implementation, and Applications[END_REF]. The definition we use in this paper is that an ontology is defined as a that are not disjoint) we also write C ≬ D and in each ontology J is the class such that J I " ∆. From classes C, D, we also form the classes C \ D, C [ D and ␣C that represent the union, intersection and complement of C (and D). In this paper, the signature of an ontology is the set of class names C P C and object names o P D.

An alignment A ab between two ontologies O a and O b with (generally) different signatures is a set of correspondences between classes of the two [START_REF] Euzenat | Ontology Matching[END_REF]. Formally, such a correspondence is a triple xC a , C b , Ry where C a and C b are class names of O a and O b , respectively, and R P tĎ, Ě, ", 'u is a relation that is asserted to hold between C a and C b . We also write C a RC b for xC a , C b , Ry.

Alignment Repair Game

The Alignment Repair Game (ARG) is a protocol designed for adaptive agents to evolve alignments between their ontologies through their use [START_REF] Euzenat | First Experiments in Cultural Alignment Repair (Extended Version)[END_REF][START_REF] Euzenat | Interaction-based ontology alignment repair with expansion and relaxation[END_REF]. The aim of ARG is to detect and repair mistakes in alignments whenever a communication failure occurs through application of the adaptation operators. The idea is that ultimately, by repeatedly playing ARG, the alignments converge towards better alignments.

Definition 3.1 (Adaptation Operator

). An adaptation operator provides a strategy for agents to revise the failing correspondence of the alignment. It specifies, given the failure of the correspondence xC a , C b , Ry with R P tĚ, "u and failing object o, what the agents should do. In [START_REF] Euzenat | First Experiments in Cultural Alignment Repair (Extended Version)[END_REF][START_REF] Euzenat | Interaction-based ontology alignment repair with expansion and relaxation[END_REF] From the definition, every operator entails delete, the operators add, addjoin, refine and refadd entail replace and refadd entails addjoin and refine. Furthermore, the order of the actions that are performed by the adaptation operators does not matter. Figure 1 illustrates the effect of the adaptation operators. Definition 3.2 (Alignment Repair Game). The Alignment Repair Game is played by a set of agents A with a common set D of objects. Each agent a P A is associated with an ontology O a and a set tA ab u of non-empty alignments is given between any two ontologies O a and O b that at least includes J a " J b . We write O i P O i for the most specific class (Ď-wise) of object o P D available in O i .

At each round of the game:

(1) Two agents a, b P A and an object o P D are picked at random.

J a Ď Ď ' D a Ď C a Ď o J b C b Ď Ď D b Ď Ď ' Ě Ď (replace) Ě (add) Ě (addjoin) Ě (refine)
(3) Agent a compares C a with O a . If O a ⊨ O a Ď C a , then
the round is a success, else the round is a failure and an adaptation operator α xC a ,C b ,Rypoq is applied to A ab .

ARG consists of a fixed number of rounds as described above for a chosen operator.

As an illustration of one ARG round consider Example 3.3 that will serve as a running example throughout this paper. Note that each class in the ontology corresponds to the conjunction of the class label and the label of its ancestors. For instance, the bottom-leftmost class in Figure 2 is defined by Square a [ Small a . The initial alignment A ab is represented by the dotted red correspondences between classes of their ontologies. Now, consider two cases: the object ▲ and the object △. Let in both cases agent a ask agent b to which class the object belongs in her ontology so that it can be translated to O a via the alignment. In both cases, agent b will answer Small b as both objects belong to this class in O b . However, while for the object ▲ the round would be successful (because ▲ P Black a ), for the object △ a failure is reached (because ▲ P W hite a and W hite a ' Black a ).

In the latter case α xBl ack a ,Small b ,"yp▲q is applied to the alignment A ab . An ARG state is the state of the alignments reached after a, possibly empty, sequence of rounds where in each failing round an adaptation operator is applied.

J b O b Small b Larдe b Ď Ď ' Square b Trianдle b ▲, △ Ď Ď ' Square b Trianдle b Ď Ď ' J a O a Black a W hite a Ď Ď ' Small a ▲ Larдe a Ď Ď ' Small a △ Larдe a Ď Ď ' " "

Definition 3.4 (ARG State).

For an ARG game with a set A of agents, a set tO i u iPA of ontologies and a set tA i j u i,jPA of alignments, an ARG state tA 1 i j u i,jPA is the set of alignments A 1 i j reached from tA i j u i,jPA after a, possibly empty, sequence of rounds.

For an ARG state s, we also write α xC a ,C b ,Rypoq psq for the result of applying the adaptation operator α to s with failing correspondence C a RC b and object o, or simply αpsq when the correspondence and object are clear from the context.

Example 3.5 (Running Example).

In case of a failure of the correspondence Black a " Small b , an adaptation operator is applied, adding the following new correspondences to the alignment and deleting the initial correspondence:

' delete: none ' replace: Black a Ď Small b ' add: J a Ě Small b ' addjoin: J a Ě Small b ' refine: Black a Ě pSquare b [ Small b q ' refadd: J a Ě Small b and Black a Ě pSquare b [ Small b q
By playing ARG with different operators, they can be compared. In Euzenat [START_REF] Euzenat | First Experiments in Cultural Alignment Repair (Extended Version)[END_REF][START_REF] Euzenat | Interaction-based ontology alignment repair with expansion and relaxation[END_REF], the operators are compared experimentally in terms of success rate (ratio of successes over rounds played), semantic precision and recall with respect to the known correct reference alignment (the degree of correctness and completeness of the resulting alignment) and convergence (the number of rounds needed to converge). It was found that all the operators have a relatively high success rate, yet do not reach 100% precision, and that recall and convergence both increases with operators that add new correspondences. The operator refadd, followed by add, shows the highest semantic recall and replace, again followed by add, the slowest convergence.

Dynamic Epistemic Logic

Dynamic Epistemic Logics (DEL) are a family of modal logics describing information flow in multi-agent systems. DEL has been widely used as a formal framework to model agent communication [START_REF] Van Benthem | Logics of communication and change[END_REF][START_REF] Plaza | Logic of public communications[END_REF][START_REF] Van Ditmarsch | Dynamic epistemic logic[END_REF], belief revision [START_REF] Van Benthem | Dynamic logic for belief revision[END_REF] and agent interaction [START_REF] Van Benthem | Logical dynamics of information and interaction[END_REF]. As such, it provides a solid basis to study knowledge and belief evolution of logical agents playing ARG. Here we consider the syntax and semantics introduced by Baltag, Moss and Solecki [START_REF] Baltag | The Logic of Public Announcements and Common Knowledge and Private Suspicions[END_REF]. Definition 3.6 (Syntax of DEL). The syntax, L DEL , of (multiagent) DEL is defined in the following way:

ϕ ::" p | ϕ ^ψ | ␣ϕ | K a ϕ | B a ϕ | r †ϕsψ
where p P P is a proposition, K a and B a are the knowledge and belief operators for each agent a and †ϕ with † P t!, Òu the dynamic upgrades.

The connectives _ and Ñ, and the duals Ka , Ba , x †ϕy are defined in the usual way: ϕ _ ψ iff ␣p␣ϕ ^␣ψ q, ϕ Ñ ψ iff ␣ϕ _ ψ , Ka ϕ " ␣K a ␣ϕ, Ba ϕ " ␣B a ␣ϕ, and x †ϕy " ␣r †ϕs␣ψ . DEL models are based on Kripke frames with plausibility relations where the logical dynamics act as model transformers.

Definition 3.7 (DEL Model).

A model of (multi-agent) DEL is a quadruple M " xW , pě a q aPA , w ˚, V y where ' W is a non-empty set of states, or worlds; ' pě a q aPA Ď W ˆW are the plausibility relations on W , one for each agent, that are converse well-founded, locally connected preorders; ' w ˚P W is the actual world; ' and V is a propositional valuation mapping propositions to sets of worlds in which that proposition is true.

The plausibility relation w ě a v reads as "w is at least as plausible as v for agent a" and the epistemic and doxastic relations are defined on W accordingly:

w

" a v iff w pď a Y ě a q v (1) w Ñ a v iff v P Max ď a |w| a (2)
where |w| a is the information cell (or accessible cell) of agent a at state w and is defined by:

|w| a " tv P W | w " a vu (3)
It follows from the properties of ď a and ě a that the relations " a are reflexive, transitive and symmetric, and the relations Ñ a are transitive, serial and Euclidean. Therefore they satisfy the usual properties of knowledge and belief, respectively [START_REF]Handbook of Modal Logic[END_REF][START_REF] Van Ditmarsch | Dynamic epistemic logic[END_REF]. Definition 3.8 (Semantics of DEL). The semantics for DEL is defined in the following way:

M, w ⊨p iff w P V ppq M, w ⊨ϕ ^ψ iff M, w ⊨ ϕ and M, w ⊨ ψ M, w ⊨␣ϕ iff M, w ⊭ ϕ M, w ⊨K a ϕ iff @v s.t. w " a v : M, v ⊨ ϕ M, w ⊨B a ϕ iff @v s.t. w Ñ a v : M, v ⊨ ϕ M, w ⊨r!ϕsψ iff M !ϕ , w ⊨ ψ M, w ⊨rÒϕsψ iff M Òϕ , w ⊨ ψ
where !ϕ and Òϕ act as model transformers !ϕ : M Ñ M !ϕ and Ò ϕ : M Ñ M Òϕ in the following ways, with ||ϕ|| M " tw P W | M, w |ù ϕu:

Announcement (!ϕ) Delete all '␣ϕ'-worlds from the model.

I.e. W !ϕ " ||ϕ|| M , w ě !ϕ a v iff w ě a v and w, v P W !ϕ , V !ϕ ppq " V ppq X ||ϕ|| M and pw ˚q!ϕ " w ˚;
Conservative upgrade (Òϕ) Change the plausibility orders so that the best 'ϕ'-worlds become better than all other worlds, while the old ordering on the rest of the worlds remains. I.e. W Òϕ " W , w ě Òϕ a v iff either w P Max ď a p|v| a X ||ϕ|| M q or w ě a v, V Òϕ ppq " V ppq and pw ˚qÒϕ " w ˚.

We also write † 1 ϕ; † 2 ψ for the sequence of upgrades † 1 ϕ and then † 2 ψ . The resulting model

M † 1 ϕ; † 2 ψ is equal to pM † 1 ϕ q † 2 ψ .
The intuition behind the different upgrades is that the trustworthiness of the information source may vary: it may be considered from an infallible source (announcements), or from a trusted, but not infallible source (conservative upgrades). For this reason, conservative upgrades only change the plausibility of worlds without deleting any alternatives.

Note that in all cases, w ˚remains the actual world of the model. This also means that an announcement !ϕ can only be validly performed on a model M if ϕ is true there.

DYNAMIC EPISTEMIC ONTOLOGY LOGIC

To compare adaptive agents with logical agents, we need a logical framework to model ARG. Here, we introduce Dynamic Epistemic Ontology Logic (DEOL) that is a variant of Dynamic Epistemic Logic where the propositions are object classifications (Cpxq) and class relations (C " D, C Ď D and C ' D) of a Description Logic language. This logic enables us to later capture knowledge and belief evolution in alignment repair. Definition 4.1 (Syntax of DEOL). The syntax, L DEO L , of (multiagent) DEOL is defined in the following way:

ϕ ::" Cpoq | CRD | ϕ ^ψ | ␣ϕ | K a ϕ | B a ϕ | r †ϕsψ R P tĎ, ", 'u, † P t!, Òu
where C, D, J P C, o P D, K a and B a are the knowledge and belief operators for agent a and †ϕ with † P t!, Òu are the dynamic upgrades.

The connectives Ñ and _ and the duals Ka , Ba , x †ϕy are defined as in the case of DEL.

DEOL models are plausibility models. The difference with DEL models is that instead of a valuation of propositions, we consider a domain of interpretation ∆ representing the objects and an interpretation function I assigning to each world a function interpreting each class as a set of objects of the domain.

Definition 4.2 (DEOL Model).

A model of (multi-agent) DEOL is a quintuple M " xW , pě a q aPA , w ˚, ∆, I y where ' W is the set of states, or worlds; ' pě a q aPA Ď W ˆW are the plausibility relations on W , one for each agent, that are converse well-founded, locally connected preorders; ' w ˚P W is the actual world; ' ∆ is the domain of interpretation (a set of objects);

'
M, w ⊨Cpoq iff o I w P C I w M, w ⊨C Ď D iff C I w Ď D I w M, w ⊨C " D iff C I w " D I w M, w ⊨C ' D iff C I w X D I w " H
The additional capacities of logical agents compared to the original game are that logical agents can now use the relations between concepts to reason about instance classification. For instance, the following axiom schemata are valid:

K a pCpxqq ^Ka pC Ď Dq ñ K a pDpxqq (4)
K a pCpxqq ^Ka pC ' Dq ñ K a p␣Dpxqq (5)
In addition, agents can combine their knowledge and beliefs to obtain new beliefs. For instance, K a pC a poqq and B a pC a Ě C b q entails B a pC b poqq. In other words, agent a can transfer some of her knowledge about C a to beliefs about C b . This increased reasoning capacity of logical agents compared to adaptive agents is crucial in the results later about the correctness, partial redundancy and incompleteness of the adaptation operators.

TRANSLATION

In the previous section, we have provided a formal framework for knowledge and belief evolution in alignment repair. We now use this framework to capture the Alignment Repair Game. More precisely, we define a translation from ARG states to DEOL axioms that are interpreted as sets of DEOL models ( §5.1) and from adaptation operators for ARG to dynamic upgrades on DEOL ( §5.2), see Figure 3. These translations are labeled by z and δ , respectively, and the interpretation on DEOL models by I . This enables us to define and prove correctness, redundancy and completeness of the adaptation operators in the remainder of this paper. In the interpretation on DEOL models, this means that the sentences that describe O a are true in any world in |w ˚|a , and the sentences that describe A ab are true in all most plausible worlds in both |w ˚|a and |w ˚|b .

Example 5.1 (Running Example). In the running example, this means that the sentences pSquare a [ Small a q Ď Small a , Small a Ď J a , Trianдle a [ Small a p▲q, etc, are true in every accessible world for agent a and that the sentences Small a " Black a and J a " J b are true in the most plausible worlds for both agents. Formally, this is achieved on the interpretation on DEOL models by ultimately making as many copies of the worlds describing the agent's knowledge and belief as there are combinations of the alternatives above, ranking them all equally plausible while respecting the order imposed by the alignments.

Because models rapidly explode, we will only draw the information given by the ontologies and alignments.

Dynamics

During the gameplay of ARG, new information is learned. There are two dynamic acts involved in the learning: the communication of C b poq in step 2 of ARG and the adaptation operator applied in step 5 (see Definition 3.2). How do these acts change the knowledge and beliefs of the agents? And are the adaptation operators as defined by Euzenat [START_REF] Euzenat | First Experiments in Cultural Alignment Repair (Extended Version)[END_REF][START_REF] Euzenat | Interaction-based ontology alignment repair with expansion and relaxation[END_REF] sufficient to account for these changes?

In order to answer these questions, we translate the communication taking place in ARG to dynamic upgrades on DEOL.

where δ pα xC a ,C b ,Ěypoq q denotes the translation of adaptation operator α applied to the correspondence C a Ě C b with failing object o.

Given that C b poq is knowledge to agent b, the communication of this information in step 3 of ARG translates to an announcement on DEOL. For the adaptation operators, announcements are not the correct tool: adaptation operators tell the agents how to revise the alignment, their beliefs, upon a communication failure. Therefore adaptation operators translate to conservative upgrades.

δ pdeleteq " Ò pC a Ğ C b q δ preplaceq " Ò pC a Ğ C b q δ paddq " Ò pC a Ğ C b ^Csup a Ě C b q δ paddjoinq " Ò pC a Ğ C b ^CsupO a Ě C b q δ prefineq " Ò pC a Ğ C b ^ľtC a Ě C sub b uq δ prefaddq " Ò pC a Ğ C b ^CsupO a Ě C b ^ľtC a Ě C sub b uq
where The upgrades for the other adaptation operators remain the same.

C sup a " Min Ď tC P O a | C a Ĺ Cu, C
Again, as was the case for the adaptation operators on ARG states, δ paddq, δ paddjoinq, δ prefineq and δ prefaddq entail δ preplaceq, and δ prefaddq entails δ paddjoinq and δ prefineq.

Example 5.6 (Running Example -Success). When ARG is played with ▲, agent b announces that !Small b p▲q and the correspondence used is xBlack a , Small b , "y P A ab . This information is compatible with the information of agent a: Black a is compatible with Small a [ Black a , i.e. the most specific class of ▲.

Compared to ARG where the round is now finished, there are additional epistemic-doxastic changes on the corresponding DEOL model. The announcement carries more information than just indicating that the round of ARG was a success, it transforms some beliefs of agent a into knowledge: B a pSmall b p▲qq becomes K a pSmall b p▲qq. In other words, agent a is now given concrete evidence that ▲ is a member of Small b whereas before she only believed this. Figure 4 can be compared to and the upper schema of Figure 5 for an overview of the changes to the epistemic-doxastic state of agent a. Example 5.7 (Running Example -Failure). If instead ARG is played with △, the round is a failure. Agent b announces !Small a p△q using the same correspondence xBlack a , Small b , "y P A ab . However, this information contradicts the knowledge of agent a and, as a result, the correspondence (belief) of the alignment will be dropped.

J b Small b ▲ △ J a O a Black a W hite a Ď Ď ' Small a ▲ Larдe a Ď Ď ' Small a △ Larдe a Ď Ď ' " ı Ę Ě Ď Ě Ě ≬ ' ' Ď J b Small b ▲ ␣ △ J a O a Black a W hite a Ď Ď ' Small a ▲ Larдe a Ď Ď ' Small a △ Larдe a Ď Ď ' " " Ď Ě Ď Ě Ě ' ' ' Ď
However, this is not the only revised belief. The contradicted initial beliefs turn into knowledge of their negation. For example, B a p␣Small b p△qq becomes K a pSmall b p△qq after the announcement.

Compare also Figure 4 and the lower schema of Figure 5 for an overview of the changes to the epistemic-doxastic state of agent a.

According to ARG, an adaptation operator is applied, which results in an updated alignment as explained in Example 3.5. These correspondences should be amongst the beliefs of the agents at the end of the round of ARG. However, for some operators, the correspondences are already believed by agent a before the adaptation operator is applied. We will see why in the next section.

The translation provided in this section is faithful because the semantics of ontologies and alignments we use is the same as in Description Logic and the only dynamic epistemic component arises from modeling the agents' knowledge and beliefs, see also [START_REF] Baader | Extensions to Description Logics[END_REF]. A formal proof is out of the scope of this paper.

FORMAL PROPERTIES OF THE ADAPTATION OPERATORS

With the formal representation of ARG in DEOL we can explore the correctness, redundancy and completeness of the operators. For this, we consider the diagram as pictured in Figure 3.

Correctness

To show that the adaptation operators are correct, we need to show that the diagram of Figure 3 commutes. Definition 6.1 (Correctness). Adaptation operator α is correct if and only if @s: pzpsqq δ pα q ⊨ zpαpsqq.

Proposition 6.2. The adaptation operators delete, replace, addjoin, refine and refadd are correct.

Proof. We do the proof for agent a and adaptation operator addjoin. The proof for replace now follows because it is entailed by addjoin, and the proof for refine is symmetric.

Because addjoin only adds beliefs, it suffices to show that these are entailed: Ě C b q are enforced for agents i P ta, bu. Hence addjoin is correct. □ Yet, the adaptation operator add is not correct because it does not take into account whether the immediate superclass of C a is consistent with the object o. And if it is consistent, add is equivalent to addjoin. Proposition 6.3. The adaptation operator α " add is incorrect, i.e. Ds : pzpsqq δ paddq ⊭ zpaddpsqq, and @s s.t. pzpsqq δ paddq ⊨ zpaddpsqq: addpsq " addjoinpsq. , i.e. add is equivalent to addjoin. □ Proposition 6.3 is in line with initial predictions and experimental results by Euzenat [START_REF] Euzenat | Interaction-based ontology alignment repair with expansion and relaxation[END_REF][START_REF] Euzenat | NOOR[END_REF]: addjoin shows faster convergence than add. This is because add can force false correspondences to be added to the alignment that can later cause a failure. From these results, it is clear that for a logical agent, add should be abandoned.

pzpsqq !C b poq;ÒpC a ĞC b ^CsupO a ĚC b q ⊨ B i pC a Ď C b q Bi pC

Redundancy

The redundancy of some operators in the running example is not a coincidence. For logical agents, i.e. DEOL agents, some adaptation operators are redundant for every ARG state: delete, replace and addjoin are redundant with respect to agent a and refine is redundant with respect to agent b. Before we define this redundancy with respect to one agent (partial redundancy), let us first consider what it means for an operator to be redundant (with respect to both agents). An adaptation operator α is redundant if and only if solely applying !C b poq on the DEOL translation of s is already sufficient to obtain an interpretation of the DEOL translation of αpsq. The adaptation operators discussed here are not redundant, but partially redundant. This means that they are redundant with respect to one agent. To prove redundancy, we show that the knowledge and belief of this agent are invariant to the application of the adaptation operator. In fact, because adaptation operators only alter the beliefs of agents, it suffices to show partial redundancy by showing that the beliefs of that agent remain unchanged. Proof. We do the proof for agent a and the adaptation operator addjoin. The proof for replace now follows because it is entailed by addjoin, and the proof for refine is symmetric.

Thus we need to show that pzpsqq !C b poq ⊨ B a ϕ implies that zpaddjoin xC a ,C b ,Ěypoq psqq ⊨ B a ϕ. So consider a sentence ϕ that is not believed by agent a in zpaddjoin xC a ,C b ,Ěypoq psqq, but is in zpsq. By construction of the dynamics of the operator addjoin, this can only be ( 1 However, none of the adaptation operators are redundant with respect to both agents. Even the simple delete carries valuable information to agent b: namely that the initial correspondence fails. Without this operator, agent b would not be aware whether the round of ARG is a success of a failure.

Incompleteness

Finally, we consider completeness of the adaptation operators: do the operators capture all the information that can be learned? Intuitively, this is proven by comparing what is learned by the agents in ARG scenarios from application of the adaptation operators with what is learned by logical agents in DEOL from the dynamic upgrades. If the former implies the later, the operator is (epistemically) complete. Definition 6.7 (Completeness). Adaptation operator α is complete if and only if @s: zpαpsqq ⊨ pzpsqq δ pα q . Proposition 6.8. All adaptation operators (delete, replace, add, addjoin, refine, refadd) are incomplete.

Proof. Again, consider the knowledge and belief of agent a before and after the announcement !C b poq, see also Figure 7. After the announcement !C b poq, agent a receives concrete information that object o belongs to the class C b , i.e. she comes to know this information: pzpsqq !C b poq ⊨ K a pC b poqq. And, by definition, this knowledge remains after application of any conservative upgrade, i.e. pzpsqq δ pα q ⊨ K a pC b poqq. Yet, this knowledge is never acquired through application of the adaptation operators because they only concern the alignment, i.e. beliefs of class relations, and not knowledge of instance classification. Hence zpαpsqq ⊭ K a pC b poqq and zpαpsqq ⊭ pzpsqq δ . □

The incompleteness proof of the adaptation operators relies on the agent not memorizing the failure of the correspondence with the drawn object. Yet, from Figure 7 it is clear that there is more knowledge gained by the agents from the announcement !C b poq. This occurs because we measure completeness, and correctness, with respect to the full knowledge and belief of the agent. When concentrating on the alignment only, as expressed by adaptive agents, the operators may be complete.

DISCUSSION AND CONCLUSION

We developed a theoretical framework for knowledge and belief evolution in ARG and formally defined correctness, completeness and redundancy of adaptation operators to compare adaptive agents and logical agents. We complement the current experimental approach by proving that, in this framework, all but the add operator are correct, delete, replace, addjoin and refine are redundant for one agent and that all operators are incomplete. This contributes to theoretically comparing the different operators and could inspire new adaptation operators for ARG. However, this does not mean that the adaptive agents are meaningless. In fact, the adaptive agents in [START_REF] Euzenat | First Experiments in Cultural Alignment Repair (Extended Version)[END_REF][START_REF] Euzenat | Interaction-based ontology alignment repair with expansion and relaxation[END_REF] implement deliberately a 'sublogical' behavior and the experiments show that, in some cases, they can perform well. For instance, agents do not need to be fully complete, and not even fully correct, to reach 100% success in ARG. The purpose of our work is to examine them under a logical light. We compare adaptive agents to logical agents, and we prove the logical limitations of the adaptation operators.

Yet, the scope of this paper lays beyond ARG. We have provided a theoretical framework that can be extended to establish formal properties of other games that are designed for agents to improve and repair alignments through interaction. This allows for a theoretical comparison of different dynamic matching algorithms.

In this paper, public signature awareness was a prerequisite in the translation from ARG states to DEOL to capture the dynamics of the game by announcements and conservative upgrades. In the future, we want to drop this prerequisite. We suspect that this might provide the means to capture the ability to generate new (random) correspondences [START_REF] Euzenat | Interaction-based ontology alignment repair with expansion and relaxation[END_REF].

  quintuple O " xD, C, Ď, ', Py where D is a set of objects, C is a non-empty set of class names, Ď, ' Ď C ˆC are the semantic relations, and P Ď D ˆC is the membership relation. To give meaning to these relations an interpretation I " x∆, ¨I y is provided specifying a domain ∆ and a function ¨I assigning to object names o P D an element in the domain ∆ and to class names C P C a set of elements of ∆. We then say that "C is subsumed by D" (C Ď D) iff C I Ď D I , "C and D are equivalent" (C " D) iff C Ď D and D Ď C, "C and D are disjoint" (C ' D) iff C I X D I " H and "o is a member of C" (o P C) iff o I P C I . We also write O ⊨ C Ď D, O ⊨ C " D, O ⊨ C ' D and O ⊨ Cpoq, respectively. For two classes C, D that overlap (i.e.

  the following adaptation operators are introduced: ' delete: delete the correspondence from A ab ; ' replace: replace the correspondence by C a Ď C b ; ' add: in addition to replace, add the correspondence C sup a Ě C b between C b and the immediate superclass C sup a of C a ; ' addjoin: in addition to replace, add the correspondence C supO a Ě C b between C b and the lowest superclass C supO a of C a that is compatible with the object o (i.e. C supO a poq); ' refine: in addition to replace, add the correspondences C a Ě C sub b between C a and all the subclasses C sub b of C b that are not compatible with the object o (i.e. ␣C sub b poq); ' refadd: addjoin and refine. We write α xC a ,C b ,Rypoq for the application of adaptation operator α to correspondence xC a , C b , Ry with failing object o.

Figure 1 :

 1 Figure 1: Schematic diagram of the deleted (red, solid) and added correspondences (blue and green, dashed and dash dotted) by the different adaptation operators in ARG.

( 2 )

 2 Agent a asks agent b to which class in his ontology the object o belongs so that it can be translated to agent a's ontology via the alignment. Agent b answers C b (with O b ⊨ C b poq and xC a , C b , Ry P A ab where R P tĚ, "u).

Example 3 . 3 (

 33 Running Example). Let agent a and agent b play ARG where their ontologies O a and O b are described in Figure 2.

Figure 2 :

 2 Figure 2: The ontologies (black) of agent a (left) and agent b (right) and the alignment (red, dashed) between them of Example 3.3.

  and I is an interpretation function s.t. I pwq " ¨Iw and ¨Iw : C Ñ Pp∆q, where it holds that J I w " ∆, and for any two classes C, D P C we have that pC [ Dq I w " C I w X D I w and p␣Cq I w " ∆ z C I w for each w P W . We also write C \ D for the class defined by ␣p␣C [ ␣Dq, and [tC i u and \tC i u for the classes defined by C 1 [ C 2 [ . . . and C 1 \ C 2 \ . . ., respectively. Their interpretations at world w are given by C I w Y D I w , Ş C I w i and Ť C I w i , respectively. In each DEOL model K " ␣J is the empty class. The semantics of DEOL is equivalent to that of DEL except that we now have instance classifications Cpoq and class relations C Ď D, C " D and C ' D.

Definition 4 . 3 (

 43 Semantics of DEOL). The semantics for DEOL extends that of DEL (Definition 3.8) by:

Figure 3 :

 3 Figure 3: Diagram of translations from ARG states to DEOL axioms (z) that are interpreted by sets of DEOL models (I ), and from adaptation operators to dynamic upgrades (δ ).

5. 1

 1 Semantics of ARG statesLet agents a and b play ARG with ontologies O a and O b , respectively, and alignment A ab . Given the nature of ontologies and alignments, we impose the following three conditions on the DEOL axioms describing the epistemic-doxastic states of agents a and b: Ontology Knowledge (OK) O a (O b ) is known to agent a (b); Alignment Belief (AB) A ab is believed by agents a and b and; Public Signature Awareness (PSA) The signatures of all ontologies are known to all agents.

  Public signature awareness ensures that agents are allowed to update their information when we consider the dynamics of the adaptation operators. It requires that, for each agent a, each object o P D and for each two classes C, D P O b with b ‰ a and not appearing in the alignment, i.e. C, D R tC b P O b | xC a , C b , Ry P A ab , C a P O a , R P t", Ď, Ě, 'uu, agent a considers all combinations of the following alternatives equally plausible: ' Cpoq and ␣Cpoq ' Dpoq and ␣Dpoq ' C " D and C ı D ' C Ď D and C Ę D ' C Ě D and C Ğ D ' C ' D and C ≬ D

Example 5 . 2 (

 52 Running Example).

Figure 4 Figure 4 :

 44 Figure 4: Initial knowledge (solid black lines) and belief (dashed red lines) of agent a in the Running Example.

Definition 5 . 4 (

 54 ARG Dynamics in DEOL). We model each round of ARG as defined in Definition 3.2 by !C b poq; if ␣C a poq then δ pα xC a ,C b ,Ěypoq q

Definition 5 . 5 (

 55 Adaptation Operators as Dynamic Upgrades). Let xC a , C b , Ěy P A ab be the failing correspondence with object o, the adaptation operators (α xC a ,C b ,Ěypoq ) are translated to the following dynamic upgrades on DEOL (where the subscript xC a , C b , Ěypoq is left out for readability):

"

  Min Ď tC P O a | C a Ĺ C ^Cpoqu (and by construction of the ontologies, C sup a and C supO a are unique) and tC a Ě C sub b u " tC a Ě C | C P O b ^C Ď C b ^Cpoqu. If the initial correspondence of the alignment is an equivalence-relation, i.e. if xC a , C b , "y P A ab , then the corresponding dynamic upgrade for delete is Ò pC a Ğ C b ^Ca Ę C b q.

Figure 5 :

 5 Figure 5: The knowledge (solid black) and belief (dashed red) of agent a of Example 3.3 after the announcement !Small b p△q (above) and after the announcement !Small b p▲q (below).

Ě

  C b q. This holds because initially the correspondence is believed, i.e. zpsq ⊨ B i pC a Ě C b q, and the upgrade !C b poq; Ò pC a Ğ C b ^CsupO a Ě C b q deletes all the worlds from zpsq in which C b poq is false and then rearranges the remaining worlds such that the 'C a Ğ C b ^CsupO a Ě C b '-worlds become more plausible that the '␣pC a Ğ C b ^CsupO a Ě C b q'-worlds. Because there remain 'C a Ğ C b ^CsupO a Ě C b '-worlds accessible for both agents, the belief is enforced. For agent b, this is true because the announcement !C b poq does not alter her epistemic-doxastic state (she already knew that C b poq as it is in her ontology), and for agent a, because the announcement !C b poq deletes the worlds in which C a Ď C b (␣C a poq holds because the correspondence and announcement caused a failure) or C a " C b but not those in which C a Ğ C b or C supO a Ě C b . Therefore the beliefs B i pC a Ď C b q and B i pC supO a

  Proof. We need to prove the existence of an ARG state s where pzpsqq δ paddq ⊭ zpaddpsqq with upgrade δ paddq "!C b poq; Ò pC a Ğ C b ^Csup a Ě C b q, object o s.t. O b ⊨ C b poq and xC a , C b , Ěy P A ab the failing correspondence. Pick s to be any such ARG state where the immediate superclass C sup a of C a is incompatible with o, i.e. O a ⊭ C sup a poq. Then zpsq ⊨ K a p␣C sup a poqq and pzpsqq δ paddq ⊨ K a pC b poqq ^Ka pC sup a Ğ C b q. This is because δ paddq deletes all '␣C b poq'-worlds from zpsq and therefore also all the worlds accessible by agent a where C Ě C b for C such that zpsq ⊨ K a pCpoqq. In particular, this holds for C sup a . But, after applying the adaptation operator add, xC sup a , C b , Ěy becomes part of the alignment, so that zpaddpsqq ⊨ B a pC sup aĚ C b q. Hence pzpsqq δ paddq ⊭ zpaddpsqq. Moreover, whenever pzpsqq δ paddq ⊨ zpaddpsqq it must be that O a ⊨ C sup a poq so that, per definition, C

Definition 6 . 4 (Figure 6 :

 646 Figure6: Diagram of translations between ARG states DEOL axioms that are interpreted on DEOL models, adaptation operators and dynamic upgrades as in Figure3where the operators are redundant.

Definition 6 . 5 (

 65 Partial Redundancy). An adaptation operator α is partially redundant for agent a if and only if pzpsqq !C b poq ⊨ B a ϕ implies zpαpsqq ⊨ B a ϕ for each ARG state s and each ϕ in L DEO L . Proposition 6.6. The adaptation operators delete, replace and addjoin are partially redundant with respect to agent a, and refine is partially redundant with respect to agent b.

Figure 7 :

 7 Figure 7: The knowledge (solid black) and beliefs (dashed red) of agent a before (left) and after (right) the announcement !C b poq.

ACKNOWLEDGMENTS

The authors thank the anonymous reviewers for their valuable comments and helpful suggestions. This work has been partially supported by MIAI @ Grenoble Alpes (ANR-19-P3IA-0003).


Heraldo Borges

Murillo Dutra

Amin Bazaz

Rafaelli Coutinho

Fábio Perosi

Fábio Porto

Florent Masseglia

Esther Pacitti

Eduardo Ogasawara
email: eogasawara@ieee.org.

Spatial-Time Motifs Discovery

Keywords: Motifs, Spatial-Time Series, Seismic

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

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 massive databases from many sources, types, and formats. However, 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]. A particular pattern that occurs a significant number of times in time series is denominated motif [START_REF] Keogh | On the Need for Time Series Data Mining Benchmarks: A Survey and Empirical Demonstration[END_REF].

The discovery of motifs 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], and computation biology (such as protein discovery) [START_REF] Hertz | Identifying DNA and protein patterns with statistically significant alignments of multiple sequences[END_REF][START_REF] Lin | Finding Motifs in Time Series[END_REF]. A vast number of motifs 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 motifs 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][START_REF] Yeh | Matrix profile VI: Meaningful multidimensional motif discovery[END_REF].

However, various important time-series phenomena present different behaviors when observed at points of space (for example, series collected by sensors and IoT) and are better modeled as spatial-time series, in which each time series is associated to a position in space. Under such scenarios, motifs might not be discovered when we restrict the analysis to the time-only dimension.

Consider, for example, the scenario where speed sensors are present in each corner of Manhattan to monitor vehicles speed. Imagine that a car accident occurs in one corner. Such occurrence decreases the vehicles speed there. It is a punctual phenomenon that might not occur again, i.e., this pattern is not observable using motif discovery techniques for univariate time series. However, due to the accident, congestions may occur in the nearby corners, decreasing vehicles speed. This pattern repeatedly occurs in the nearby corners, possibly with a time lag. It characterizes, intuitively, what we would call as a spatial-time motif. The challenge becomes to identify regions of space and time where the motifs are frequently observed. Finding patterns that are frequent in a constrained space and time, i.e., finding spatial-time motifs, may enable us to comprehend how a phenomenon occurs.

This paper tackles such problem by presenting an approach to discover and rank motifs in spatial-time series, denominated Combined Series Approach (CSA). CSA partitions the dataset into space-time blocks. Subsequences of time series inside these blocks are combined into a single time series. Then, it applies a traditional motif discovery algorithm over the combined time series to discover them. Subsequences occurring above a spatial-time threshold are selected as motifs. Finally, motifs are ranked considering their entropy, their number of occurrences, and the proximity of their occurrences.

We have evaluated our approach using Synthetic and Seismic datasets. It was able to identify spatial-time motifs that could not be identified using the traditional approach. CSA was also able to prioritize motifs that were meaningful both in the context of synthetic data and also according to seismic specialists.

In addition to this introduction, this work is organized into more seven sections. Section 2 presents the background for time series data mining. It includes a brief literature review about motifs in time series and the main concepts and techniques that support the motif discovering processes. Section 3 presents the Related Works. Section 4 formalizes the problem definition. Section 5 presents the CSA algorithm to find motifs in spatial-time series. Section 6 presents a synthetic dataset showing how the CSA behaves. Section 7 describes and explains the experiments that were made using seismic dataset. Finally, section 8 concludes.

Background

In this section, we introduce some background for the data mining process of motif discovery.

Time series background

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

t =< t 1 , t 2 , • • • , t m >, t i ∈ 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 of 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. All sliding windows of size n for a time series t are 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), ∀w i ∈ 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].

Figure 1 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.

A spatial-time series st can be described as a pair (t, p), such that a time series t 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 had 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 spatial-time series. For the sake of simplicity, from now on, we are calling them spatial-time series.

Data preprocessing

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 motif discovery, processing directly numerical representation is not efficient [START_REF] Daw | A review of symbolic analysis of experimental data[END_REF]. Due to that, during motif 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 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 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 i in a range varying from [0, 1], as shown in Equation 2 [START_REF] Ogasawara | Neural networks cartridges for data mining on time series[END_REF].

t i = (t i -µ t ) σ t (1)
t i = t i -min(t) max(t) -min(t) (2)
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 ], • • • , [β n-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].

Motif

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), moti f (q, t, σ) ↔ ∃ R ⊆ W, (|R| σ), such that ∀w i ∈ 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.

The heuristic-based algorithms include methods such as random projections. The goal is to reduce the search space. The random projection was proposed to handle large dataset by reducing dimensionality. It randomly selects some of sliding windows columns for search [START_REF] Li | Probabilistic discovery of motifs in water level[END_REF]. The technique optimizes the execution time in discovering motifs [START_REF] Chiu | Probabilistic discovery of time series motifs[END_REF][START_REF] Buhler | Finding motifs using random projections[END_REF]. It adopts a collision matrix that is built by masking the projected columns of both the subsequence matrix and candidate search sequence. If they match, then the sequence is placed in a hash structure for full comparison.

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].

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]. Castro and Azevedo [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.

Related Works

There are two recent review papers regarding motif discovery that characterize researches and trends [START_REF] Mueen | Time series motif discovery: Dimensions and applications[END_REF][START_REF] Torkamani | Survey on time series motif discovery[END_REF]. Concerning spatial-time approach, there are few initiatives such as discovering motifs in trajectory data [START_REF] Oates | Motif discovery in spatial trajectories using grammar inference[END_REF] and discovering migration motifs in financial data [START_REF] Du | Migration motif: A spatial-temporal pattern mining approach for financial markets[END_REF]. Oates et al. [START_REF] Oates | Motif discovery in spatial trajectories using grammar inference[END_REF] focused on analyzing repetitive sequences of moving objects. For that, they developed a grammar, applied SAX indexing, and searched for motifs over the trajectory. In our work, we do not have a moving object. Sensors are fixed, and we analyze a phenomenon that occurs at each position throughout time.

Meanwhile, in Du et al. [START_REF] Du | Migration motif: A spatial-temporal pattern mining approach for financial markets[END_REF], space is modeled 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.

Due to the absence of directly related work for the spatial-time motif discovery, 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).

Considering the exact motif discovery approach, some specific method to address the dimensionality and motif length problem were proposed. Jiang et al. [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. Mueen et al. [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]. Narang and Bhattacherjee [START_REF] Narang | Parallel exact time series motif discovery[END_REF] 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. Mueen et al. [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. Cassisi et al. [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. Chi and Wang [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. Truong and Anh [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.

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 Chiu et al. [START_REF] Chiu | Probabilistic discovery of time series motifs[END_REF]. Lin et al. [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. Mohammad and Nishida [START_REF] Mohammad | Constrained motif discovery in time series[END_REF] proposed two algorithms called MCFull and MCInc that address constrained motif discovery problem. Castro and Azevedo [START_REF] Castro | Multiresolution motif discovery in time series[END_REF] addressed motif discovery problem as an approximate top k-frequent subsequence discovery problem. Lin et al. [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. Armstrong and Drewniak [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. Narang and Bhattcherjee [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.

Regarding variable-length motif discovery, Wilson et al. [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. Yankov et al. [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. Nunthanid et al. [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. [START_REF] Nunthanid | Parameter-free motif discovery for time series data[END_REF] 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. Mueen [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. Mohammad and Nishida [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, in multivariate time series, Tanaka and Uehara [START_REF] Tanaka | Discover motifs in multi-dimensional time-series using the principal component analysis and the MDL principle[END_REF] and Tanaka et al. [START_REF] Tanaka | Discovery of time-series motif from multi-dimensional data based on MDL principle[END_REF] showed how to dynamically determine the optimum period length using the Minimum Description Length (MDL) principle and applied the method to the multidimensional time-series transforming into one-dimensional time-series using the Principal Component Analysis. Liu et al. [START_REF] Liu | Locating motifs in time-series data[END_REF] proposed a heuristic approach that can significantly improve the quality of motifs in m-dimensional time series. Vahdatpour et al. [START_REF] Vahdatpour | Toward unsupervised activity discovery using multi-dimensional motif detection in time series[END_REF] proposed a new model based on Random Projection to find approximately motif in multivariate time series data by combining motifs discovered and grouping them. Wang et al. [START_REF] Wang | A tree-construction search approach for multivariate time series motifs discovery[END_REF] developed the AMG method to list the motifs by scanning the entire series and then filling a matrix for similarity comparison to verify the real motif. Lam et al. [START_REF] Lam | Online discovery of top-k similar motifs in time series data[END_REF] proposed two algorithms for solving multivariate time series called nmotif and kmotif. McGovern et al. [START_REF] Mcgovern | Identifying predictive multi-dimensional time series motifs: An application to severe weather prediction[END_REF] introduced an approach to multidimensional motif mining in temporal streams of real-world data. Son and Anh [START_REF] Son | Discovering time series motifs based on multidimensional index and early abandoning[END_REF] presented an R*-tree together with early abandoning based approach that stores Minimum Bounding Rectangles (MBR) of data in memory. Son and Anh [START_REF] Son | Discovery of time series k-motifs based on multidimensional index[END_REF] proposed two new algorithms for motif discovery in time series data, first based on R-tree and the other is based on dimensionality reduction through Skyline index.

Problem Definition

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 order to highlight this challenging problem, consider a synthetic dataset containing twelve spatialtime series (S T 1 • • • S T 12) as depicted in Figure 2. Each spatial-time series S T i has a position in space. The ordering of time-series obeys their spatial placement. For example, S T 2 is both close to S T 1 and S T 3.

If we apply to this scenario a known motif discovery method on each spatial-time series for a support σ 2, we can observe discovered motifs in Figure 2, which are marked as green worm-like shape found only in S T 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 (S T 2, S T 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 5 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 spatial-time series datasets can address some real-world problems. Such a scenario was not studied in previous works as discussed in section 3. 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 motifs that occur in a constrained space and time. In our work, sequences may only be frequent inside spatialtime blocks. 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 motif 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 spatial-time motifs in a spatialtime series dataset.

Combined Series Approach (CS A)

To address the defined problem, we developed the Combined Series Approach (CS A) that is organized in three main steps: (i) normalization & SAX indexing; (ii) discovery of spatial-time motifs; (iii) ranking of spatial-time motifs. CS A is summarized in Algorithm 1. It takes as input a spatial-time series dataset S , a word size w, an alphabet size a, sb and tb corresponding to spatial and temporal block sizes, and σ and κ constraints. moti f s ← discover(cs, w, σ)

7: stmoti f s ← validate(moti f s, σ, κ) ∪ stmoti f s 8: return stmoti f s 1: function rankS T Moti f s(stmoti f s) 2: stmoti f s ← group(stmoti f s) 3:
for each m i ∈ stmoti f s do 4:

ent i = | f t(mi)| k=1 f t(mi)k n • log 2 f t(mi)k n 5:
O i ← occurrences(m i )

6:

occ i ← log 2 (O i ) 7: prox i ← 1 aw(mst(wam(Oi))) 8: rank = pro j(norm(ent, occ, dist)) 9:
return order(stmoti f s, rank)

Normalization & SAX indexing

The first step of the CS A, described by the normS AX function of Algorithm 1, applies z-score data normalization in the entire dataset. Right after normalization, the 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.2. The output of such transformation is returned by the function.

Spatial-time Motif Discovery

The second step of CS A corresponds to discoverS T Moti f s function. In line 2, the indexed spatial-time series dataset S is partitioned into blocks (B). These blocks are created based on spatial block size (sb) and temporal block size (tb). The sb corresponds to 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 }. Formally, each block b i, j contains sb

• tb observations, ∀i ∈ [1, |st.t| tb ], ∀ j ∈ [1, |S | sb ]. Each block b i, j contains sb subsequences q k , such that q k = seq tb,(i-1)•(tb)+1 (S ( j-1)•sb+k .t), ∀k ∈ [1, sb].
In line 5, 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 . Formally, cs = q

1 • • • q k and |cs| = k i=1 |q i | = sb • tb.
The discover function (line 6) applies a traditional motif discovery approach. More specifically, discover function applies an adapted hash-based approach [START_REF] Xuan | An efficient hash-based method for time series motif discovery[END_REF] for exact match motif discovery [START_REF] Mueen | Enumeration of time series motifs of all lengths[END_REF] 1 . It checks all subsequences of size w in cs to discovery motifs of length w. The first step applies a hash function for registering the positions of each subsequence s i . If the number of occurrences of s i is greater than σ, s i is a temporal motif and included at moti f s. Then, in line 7, moti f 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 stmoti f s.

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 CS A, described by the rankS T Moti f s function of Algorithm 1, 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 discoverS T Moti f 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 4, 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 ( f m) for the characters presented in a motif [START_REF] Shannon | A Mathematical Theory of Communication[END_REF] and is described in line 4. The higher is the entropy; the higher is the information that motif m i encodes.

At line 5 the set of occurrences O i for the motif m i is obtained. Then, in line 6, 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 7, 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 number 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 is normalized using minmax 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 rankS T Moti f s returns the stmoti f s ordered according to the computed rank.

Analysis Using Synthetic Dataset

For a better understanding of the CS A and its steps, consider a synthetic spatial-time dataset S as depicted in Figure 2 (section 4). Each row is a spatial-time series (varying from positions 1 to 12) with 20 observations. In our example, we established the following thresholds: (i) word size (w = 4), (ii) alphabet size (a = 5), (iii) spatial block size (sb = 4), (iv) temporal block size (tb = 10), (v) thresholds σ = 2 and κ = 2. (a,b,c,d,e). In this case, central values are tagged as c, lower positive values as d, higher positive as e, lower negative as b and higher negative as a. The second step of CS A (discoverS T Moti f s) encompasses combine, discover, and validate functions. Figure 3 also shows the partitioning of the dataset according to CS A, where each orange box corresponds to a block. Since the dataset has 12 spatial-time series and 20 observations, the dataset is divided into 6 blocks, where each one contains 40 observations.

Figure 4 shows the result of the combine and discover functions presented in the discoverS T Moti f s to our synthetic dataset. Each block produces a combined time series (cs) with 40 observations. In each cs, the discover identifies all motif with σ 2. The motifs discovered are marked with colors red, green, and orange. Then, motifs are depicted at their original position concerning the dataset (as presented in Figure 5) as long as they are validated according to both σ and κ constraints.

The majority of motifs discovered using the CS A approach had not been found when applying traditional motif discovery algorithms on each spatial-time series. As indicated in Table 1, traditional approach (Trad.) only found two occurrences for motif baba (marked as green). CSA found four occurrences of baba, seven of bded (marked as red), and two sets of three ceeb (marked as orange). In the case of bded, the seven occurrences were discovered in neighboring blocks and were grouped in a single set. However, in the case of ceeb, the two sets of three occurrences were not grouped since they were not found in neighboring blocks.

Table 1 also presents the dimensions used to rank the identified motifs. The entropy (Ent.) for both bded and ceeb was 1.5 since they contain three out of four distinct characters. The proximity metric (Prox.) is the reciprocal of the average weight of the minimum spanning tree that connects identified occurrences for each motif (the closer to one, the better it is). Thus, baba presents better proximity (0.83). The occurrences (Occ.) consider the log 2 of the occurrences. Finally, the ranking (Rank) combines the normalized dimensions (Ent., Prox. and Occ.) projecting it to normalized vector ( 13 , 1 3 , 1 3 ). The motif bded was the better ranked one (1.52) followed close by set ceeb(1) that occurred from S T 10 to S T 12 (1.17). Although ceeb has better proximity, the number of occurrences of bded compensated this measure. Finally, even though baba had a lower entropy, it was better ranked than ceeb(2), which occurred from S T 1 to S T 4, due to better occurrences and proximity values.

Analysis Using Seismic Dataset

As a proof of concept evaluation, we applied CSA on the Netherlands seismic spatial-time series dataset, named F3 Block [START_REF]Netherlands Offshore F3 Block -Complete[END_REF]. The database produced by the seismic reflection method was collected in a region located in the Dutch sector of the North Sea. This method consists of generating artificial seismic 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 time of arrival 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. This method is analogous to imaging the human body using ultrasound. However, unlike medicine, where the density contrasts are imaged, on seismic exploration, the effect of the acoustic impedance difference is more studied [START_REF] Zhou | Practical Seismic Data Analysis[END_REF].

In 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 the inline 401 since it has been mapped by seismic specialists who have annotated some relevant information. Figure 6 shows the inline 401. Inline 401 consists of 920 spatial-time series with 440 observations in each. The horizontal axis represents the position of the receivers and vertical axis represents the time, which is also related to the depth at the subsoil.

The value of observations represents the wave amplitude reflected from the subsoil at a particular position and depth. Figure 7 depicts the probability density function (PDF), where it is possible to observe a frequency distribution with a high concentration of values close to zero and with values mainly varying from -10000 to 10000. Also, the data available is free from noise and missing values. In contrast to the synthetic dataset, depicted in Figure 3, in this dataset spatial-time series are displayed vertically.

Experimental Setup

This section discusses the experimental setup aiming to evaluate CSA in discovering spatial-time motifs in the seismic dataset. The setup was driven for a sensitivity analysis to measure CSA performance under different aspects and also against the traditional approach designed only for time series. The CSA algorithm requires parameters alpha, word, tb, sb, σ, and κ to be specified. The description of these parameters and the range explored are summarized in Table 2. These parameters influence both the quality of results and the computation elapsed time. The alpha was chosen based on the data adjustment. We varied the alphabet size for SAX encoding from 1 to 25, and measured the Mean Squared Error (MS E) for each observation concerning the mean of each SAX character. The higher the alphabet size, the lower is the MS E. The choice for the alphabet was identified by the maximum curvature analysis as depicted in Figure 8. The point where the maximum curvature is achieved (in red) indicates that increasing more the alphabet does not bring much more benefit concerning the MS E. The CSA is available as an R Package (STMotif) 2 . The implementation, dataset, and results are also available 3 . All experimental evaluation was conducted in a cluster with 24 cores using SparkR [START_REF] Venkataraman | SparkR: Scaling R programs with spark[END_REF]. The experimental evaluation ran at wall-time of 1.3 hours.

Analysis of Spatial-Time Motifs

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. We also included the traditional approach for discovering motifs in time series against CSA.

Table 3 presents the overall performance of both the traditional approach and CSA under different block orientation for all possible parameter combinations described in Table 2. 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 the 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 the traditional approach (the square had better performance. It discovered more than 2.5 times more motifs than traditional approach).

Comparing the performance of different CSA orientation (Vertical, Square, and Horizontal), we may expect that typically Horizontal orientation might break temporal sequences. However, in our dataset, patterns often occurred in a small time interval 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 4 disclosures the results of Table 3 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 3. It can be observed that as we increase the word size, the number of discovered motifs decreases. The same behavior occurs in 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.

Table 5 presents 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. Also, as we increase κ constraint, the number of occurrences decreases.

Analysis of Top-k Spatial-Time Motifs

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 6, we computed the top-5 distinct motifs that accomplished the same criteria adopted to build Table 3. The highest-ranked motif (aagg) presented good proximity value, an average entropy value, and a high occurrences value. Such combination produced a rank value of 1.57. The second place (d f ge), although exhibiting low occurrences value, has a good proximity and entropy values. The third place (aaag) was similar to the first motif, but with lower occurrences value. The fourth place (gg f a) compensated the low occurrences value with an excellent proximity value. Finally, the fifth place (eg f 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 (Figure 9), 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. Figure 10 plots the top-ten distinct motifs sorted by their occurrences. 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. Finally, our algorithm is capable of identifying more or fewer motifs according to the used parameters. However, the meaning of the motifs and their relevance is up to the specialist evaluation.

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 paper, we tackle this problem by introducing a novel approach for spatialtime series motif discovery. To the best of our knowledge, this is the first work to propose a complete approach, named Combined Series Approach (CSA), 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 approach is isolated from actual motif discovery algorithms applied. Such property enables exploring different motif discovery algorithms, such as Random Projection and Matrix Profile, exploring the effectiveness (precision), efficiency, and scalability targeting the improvement of space-time series discovery.

We have evaluated CSA against the traditional approach using both synthetic and seismic dataset. CSA was able to identify more motifs and occurrences than the traditional approach. Also, the identified motifs were well ranked considering both spatial-time constraints, number of occurrences and the motif entropy. Due to the potential of the technique applied to a spatial-time series, it opens opportunities for exploring other real-world applications modeled as spatial-time series. There are also opportunities to automate parameters for CSA. Finally, there are also opportunities to explore different ranking functions for targeting domain-specific problems.

Fig. 1 .

 1 Fig. 1. An example of a time series, sub-sequences, and sliding windows

Fig. 2 .

 2 Fig. 2. A synthetic dataset with twelve spatial-time series: S T 1 • • • S T 12. Traditional motif discovery algorithm applied in this spatial-time series dataset finds the two green worm-like as motifs

Algorithm 1 1 : 1 : 4 :

 1114 Combined Series Approach 1: function CS A(S , w, a, sb, tb, σ, κ) 2: S ← normS AX(S , a) 3: stmoti f s ← discoverS T Moti f s(S , w, sb, tb, σ, κ) 4: rstmoti f s ← rankS T Moti f s(stmoti f s) function normS AX(S , a) function discoverS T Moti f s(S , w, sb, tb, σ, κ) 2: B ← partition(S , sb, tb) for each b i, j ∈ B do 5: cs ← combine(b i, j ) 6:

Figure 3

 3 depicts the result of applying the first step of CS A (normS AX) into the synthetic dataset. Values are being replaced by letters

Fig. 3 .

 3 Fig. 3. Synthetic dataset partitioned into blocks

Fig. 4 .Fig. 5 .

 45 Fig. 4. Motif discovery algorithm applied to combined series

Fig. 6 Fig. 7 .

 67 Fig. 6. Seismic Dataset

Fig. 8 .

 8 Fig. 8. MS E for each alphabet size

Fig. 9 .

 9 Fig. 9. Top-ten discovered motifs according to the ranking function

Fig. 10 .

 10 Fig. 10. Top-ten discovered motifs according to the number of occurrences, filtering the ones with ranking function lower than 1.0

Table 1

 1 CSA versus Traditional (Trad.) method in the synthetic dataset

	Motif	Trad.	CSA	Ent.	Prox.	Occ.	Rank
	bded	-	7	1.5	0.53	2.81	1.52
	ceeb(1)	-	3	1.5	0.71	1.58	1.17
	baba	2	4	1.0	0.83	2.00	0.95
	ceeb(2)	-	3	1.5	0.47	1.58	0.71

Table 3

 3 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 4

 4 Summary of Discovered Spatial-Time Motifs for different block orientation and word size

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

Table 5

 5 Influence of σ and κ in the number of occurrences in Square (20x20) setup with word size w = 4

				σ
	κ	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 6

 6

		Top five distinct motifs
	motif	proximity	entropy	occurrences	rank
	aagg	0.74	1.0	8.28	1.57
	d f ge	0.83	2.0	3.16	1.46
	aaag	0.85	0.8	7.06	1.45
	gg f a	1.00	1.5	3.17	1.40
	eg f a	0.75	2.0	3.17	1.39

Such an approach enables the introduction of other state-of-the-art motif discovery algorithms

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

https://eic.cefet-rj.br/~eogasawara/csa

Acknowledgements

The authors thank CNPq, CAPES (finance code 001), and FAPERJ for partially funding this research.