Modeling Trajectories: A Spatio-Temporal Data Type Approach

Modeling Trajectories: A Spatio-Temporal Data Type Approach Ali Frihida1, Donia Zheni1, Henda Ben Ghezala2, and Christophe Claramunt3 1 LTSIRS, Ecole Nationale d’Ingénieurs de Tunis, University Tunis El Manar, Tunisia 2 RIADI, Ecole Nationale des Sciences de l’Informatique, University of Manouba, Tunisia 3 Naval Academy Research Institute, France [email protected], [email protected] [email protected], [email protected]

Abstract Retrieving and analyzing trajectories favor the study of human behaviors in space and time. Although Time Geography has long proposed a conceptual framework for the interpretation of trajectory data, there is still a need for database and semantic models that support representation and manipulation. In fact, the concept of trajectory is rarely addressed as a sui generis data type that can be embedded in a database structure. This paper introduces an algebraic SpatioTemporal Trajectory data type (STT) for the representation of object trajectory. The STT is an abstract data type endowed with a set of operations designed as a way to cover the syntax and semantics of a given trajectory. It is considered as a data structure that can be used for the design and implementation of spatio-temporal databases.

1. Introduction Spatio-temporal databases systems are oriented to the integration and management of spatial, temporal and spatio-temporal concepts and data. When dealing with dynamic geographical systems, the notion of trajectory is one of the key primitives concepts of such databases. Time Geography theory defined this concept as a tagged itinerary using spatial and temporal markers to make a difference between dynamic (trips) and static (activities) states (see Fig. 1) [1], [2]. We hereafter model a trajectory as a spatio-temporal trajectory (STT). The concept of STT models a trajectory history where a series of trajectory states is depicted by persistent observations. Retrieval and analysis of STTs are expected to give insights concerning the manner a phenomenon uses to evolve (how) and the reason behind such an evolution (why).

Recent database research developed formal representations for the representation of trajectories [3] [4]. However, none of these works consider a trajectory as a persistent entity. A trajectory needs to be constructed on the fly by a set of more or less complex and ad hoc queries addressed to the objects repository. The semantics of trajectories is indirectly represented, thus hampering manipulation and query capabilities. In order to overcome this semantics limitation, there is a need to design and implement a data structure that represents adequately the semantics of a trajectory. Such a data structure is intended to be included in the available primitives of the data structure made available by an extensible spatio-temporal DBMS. This paper presents the design and validation of a STT type based on the abstract data type approach (ADT). The reminder of the paper is organised as follows. Section 2 briefly introduces related work in the representation of trajectories using abstract data types. Section 3 defines the STT abstract data type, its syntax and semantics. Section 4 illustrates the STT type using query examples. Finally Section 5 concludes the paper and draws some perspectives.

2. Spatio-Temporal ADT: Related work An abstract data type (ADT) can be informally defined as a specification of a set of data and operations that can be performed on that data type and can be called by a developer. An ADT can be defined algebraically, or can be implemented as an interface (i.e., publicly available operations). A spatio-temporal ADT was first introduced in early researches initiated in [5]. Through a series of papers [5][6][7][8], [9] several authors have developed and implemented an algebraic ADT approach for moving geometries, like moving point and moving regions. However, these approaches did not consider the semantics dimension

as these trajectories have been considered from a purely geometrical point of view. The only form of semantic representation is expressed through derivative operations allowing the request of some kind of “semantic” trajectory properties. These properties are those derivable from the data, e.g., moving object’s speed or velocity. Based on Güting’s approach [6], [10] proposed a data type-oriented model for moving objects. This approach, so-called HERMES framework, was implemented as an Oracle data cartridge. Despite their interest, none of these approaches consider semantic information over trajectories. In [11], a particular attention is drawn to formally-defined future trajectories, but still with no specific integration of trajectory semantics. In [12], an algebra for network-constrained moving objects is defined. This model introduced network, gpoint and gline data types to represent a network, a position on a network, or a region within the network. A relative representation of trajectories has been introduced to apprehend the dynamics of motion taking into account relative basic primitives like velocities and orientation [13]. The common trend of the models described above is that no qualitative analysis on the way an object moves or the goal of a given trajectory can be done, this being due to the fact that the semantics behind is limited to geometry. To overcome these limitations, [14] proposed a conceptual model that addresses trajectories as movements that correspond to semantically meaningful travels. The semantic view of a trajectory is based on basic concepts of Time Geography and discussed at the conceptual level but data acquisition, retrieval and spatial operations are non formally presented. Another contribution introduced an algebraic model for representing changes at the conceptual level but with no explicit consideration of trajectories [15]. Overall, most of these research efforts are either oriented towards geometric and formal representations of trajectories, or discussed at the conceptual level. Even when implicitly considered, the semantic dimension is in fact neglected. The STT is rarely supported by a set of operations that permit manipulation of the semantic domain required to analyse the trips and activities behind the trajectories represented. Moreover, usual manipulation operations such as difference, union, intersection of STTs are not supported. The aim of this paper is to propose an algebraic model to represent and encapsulate the syntactic and semantic specification of STTs into an ADT. The proposed ADT offers a primary and persistent identity

to the STT. Henceforth, the STT is a natively defined data structure. Once integrated in a DBMS, it acquires the same status than built in and conventional data structures. This identity is supported by a set of operations covering the spatial, temporal, spatiotemporal and semantic properties and behaviours. The next section introduces the STT ADT. The syntactic definition is presented as well as the semantics encapsulated.

3. Trajectory ADT This section defines the STT ADT and operations, or algebra, suitable for representing and querying semantic-based trajectories. The modeling approach consists of two steps. The first step introduces the trajectory data type. The semantic of the proposed data type is given by a carrier set. The second step describes a collection of operations over the proposed data type. For each operation, its signature and semantics are given by defining a function on the carrier sets of the argument types.

3.1. STT ADT The definition of the STT data type requires different sorts (types). Atomic data types like real, integer, string, boolean and complex data types like alist are necessary. For the representation of spatial and temporal data, we assume the following usual data types: Point, Line, Polygon, Time and Interval. An activity description is given formally as a quadruple a = (l, ts, te, type) where l ∈ Point represents its location, ts and te ∈ Time represent, respectively, its starting time and its ending time, and type ∈ string is its data type (e.g., shopping, working). We formally define a trip as d = (ls, le, ts, te, mode, path) where ls, le ∈ Point represent, respectively, its start location and end location; ts and te ∈ Time represent, respectively, its starting time and its ending time; mode ∈ string is the mean used to make the trip. The attribute path can express either “simple” spatial information or “richer” spatio-temporal information. In the first case, the only points of interest are the activity locations. The type of motion modeled here is stepwise. In this case, the path attribute can be a line. In the second case, if one wants to represent a continuous trip, the path can itself be a sub-trajectory of type, for example, a moving point [6]. At the semantic level, a valid activity must start before it ends. The same constraint applies to trips. Thus, the set of possible activity values is denoted by

Da = {a | a.ts < a.te}. The set of possible trip values is denoted by Dd = {d | d.ts < d.te}. Within a given STT, successive activities never temporally overlap. Therefore, we denote the activity set of a STT as the temporally ordered subset A, as A = {ai | ∀ 1 ≤ i ≤ n : ai ∈ Da ∧ ai.ts < ai+1.ts ∧ ai.te < ai+1.ts}. Similarly, the trip set of a STT is the temporally ordered subset D, where D = {di | ∀ 1 ≤ i ≤ n : di ∈ Dd ∧ di.ts < di+1.ts ∧ di.te < di+1.ts}. Consequently, a value of type STT is a pair, (A,D), of temporally ordered sets. The first state of a STT is a trip d1 succeeded by its goal, which is the activity a1. The last state of the STT is the activity an. The domain of the proposed type is then formulated, on the basis of temporal and spatial constraints as follows:

3.2.2 Semantic operations. These operations allow the user to formulate queries on the semantics of the STT data type. We define data retrieval operations that return states (activities or trips) on the basis of their purpose, type, mode, temporal precedence with other states or according to their position in the TST. We also offer predicates and numeric operations. In fact, these operators may in the spirit not only be applied to activities, but also to trips. Hereafter are some examples of such operations:

DTST = {(A,D) | (1,2) ∀ 1 < i ≤ n : di.ls = ai-1.l ∧ di.ts= ai-1.te + 1 (3,4) ∀ 1 ≤ i ≤ n : di.le = ai.l ∧ di.te = ai.ts - 1}

Semantically, the behavior of these predicates can be reduced to the corresponding set-theoretic ones, and are defined as follows. Let a be an Activity, stt a STT value. Then

Constraints (1) and (3) express spatial relations between a trip and its previous and next activities. Constraints (2) and (4) express temporal relations between similar states. These constraints, together with temporal order on activities and trips, express the chaining of a STT.

3.2. Operations In order to obtain a language with an expressivity at different levels, we define a set of operations on the STT data type. These operations are categorized into five groups. 3.2.1 Creators. These operations allow creation and modification of a STT. The modification mechanism consists basically on adding or removing, in the ordered temporal chaining, a couple of trip/activity. These operations have the following signatures: Make : → STT Add : STT × Trip × Activity Sub : STT → STT

→ STT

At the semantic level, we formally define creators with interpretation functions. Let a be an Activity, d a Trip and stt a STT value. Then fAdd(stt, d, a) := (A ∪ {a}, D ∪ {d}) if (d.ls = an.l ∧ (d.le = a.l ) ∧ (d.ts = an.te +1) ∧ (d.te = a.ts -1) fSub(tst) := (A \{an}, D \ {dn}) if card(A) ≠ 0 ∧ card(D) ≠ 0

Nth_Activity : STT × integer → Activity Include_Activity : STT × Activity → boolean Activity_Before_Trip : STT × Trip → Activity Activity_With_Type : STT × string → Activity

fInclude_Activity(stt, a) := (a ⊂ A) Due to the large number of operations proposed, we introduce the semantics of a few number of them. The rest is defined according to similar principles. Let stt be a STT value, d be a Trip value, i be an integer value, and t and m be string values. Then fNth_Activity(stt, i) := ai ∈ A if 1 ≤ i ≤ n fActivity_Before_Trip(stt, d) := ai ∈ A if ∃ 1 ≤ i < n : d = di+1 fActivity_With_Type(stt, t):= ai ∈ A if ∃ 1 ≤ i ≤ n : ai.type = t fMode_of_Trip(tst, d):= di.m ∈ string if ∃ 1 ≤ i ≤ n : di = d 3.2.3 Temporal operations. This group of operations concerns essentially those expressing topological relationships in time [16]. We define these topological operations between STT/Time, Time/STT, STT/Interval, Interval/STT and STT/STT. Some examples of these operations are as follows : Time_During_STT : Time × STT → boolean Interval_After_STT: Interval × STT → boolean STT_Contains_STT : STT × STT → boolean In order to formulate the semantics of these operations, the STT is restricted to the temporal domain. At a temporal level, a STT value is equivalent to the time interval during which the trajectory is defined. This interval, is denoted by ISTT = [d1.ts, dn.te].

For example, let stt1 and stt2 be two STT values, as shown in Fig 1. Let t be a Time value. Then fSTT_Contains_STT(stt1,stt2) := Istt1 Contains Istt2 fTime_During_STT(t,stt1) := t During Istt1 fTime_After_STT(t,stt2) := t After Istt2

The predicates expressed above are true (i.e., hold) in the schema illustrated in Fig1.

The predicates expressed above are true (i.e., hold) in the schema illustrated in Fig1. 3.2.3 Spatial operations. These operations are essentially spatial predicates expressing topological relationships [17]. We define topological operations between STT/Point, Point/STT, STT/Line, Line/STT, STT/Polygon, Polygon/STT and STT/STT. Some examples are as follows: STT_EndsBy_Point : STT × Point → boolean STT_Contains_STT : STT × STT → boolean STT_Cross_Line : STT × Line → boolean STT_Inside_Polygon : STT × Polygon → boolean Time

stt1 a2

Istt1

3.2.3 Sets operations. This category of operation is specified by analogy to set-theoretic operations. The set operations are as follows: Equal : STT × STT → Boolean Union : STT × STT → Boolean Intersection : STT × STT → STT Difference : STT × STT → STT The operation of equality, for example, can be informally defined as follows: a trajectory STT1 is equal to a trajectory STT2, if these trajectories show a same spatio-temporal and semantic behavior over a given period of time. The semantic of some these operations can be defined as follows. Let stt1 and stt2 be two STT values. Then fEqual(tst1, tst2) := true if card(tst1.A) = card(tst2.A) ∧ ( ∀ 1 ≤ i ≤ n : tst1.ai = tst2.ai ∧ tst1.di =tst2.di ) fUnion(tst1, tst2) := {(tst1.A ∪ tst1.A , tst1.D ∪ tst2.D )} if (tst2.d1.ls = tst1.an.l ) ∧ (tst2.d1.ts = tst1.an.te +1)

stt2

t

fSTT_Cross_STT(stt1,stt2) := lstt1 Cross lstt2 fline_Disjoint_STT(l,stt1) := l Disjoint lstt1

d2

Istt2

a1

4. Query examples

d1

lstt1

lstt2

Space

lstt : Spatial restriction of STT Istt : Temporal restriction of STT

Figure 1. Spatial and temporal restrictions of STT

In the spatial domain, a STT value is equivalent and thus treated as a line value, denoted by lSTT. This line represents the path (i.e., itinerary) followed by the moving entity during its different trips. This path is generated by the concatenation of the line set di.path, for 1 ≤ i ≤ n. In the case of a continuous change, a path attribute is, for example, a moving point. A single trip path can be generated by using the trajectory : mpoint → line operation [6]. Then, lSTT will be the concatenation of the line set trajectory(di.path), for 1 ≤ i ≤ n. Let stt1 and stt2 be two STT values, as shown in Fig1 Let l be a line value. Then

In order to illustrate the capabilities of the query language, this section formulates several illustrative queries. Let us assume an application that models daily patterns of person activities. Every person generates several activity patterns corresponding to a period of time. After a sequence of activity data collection, spatial, temporal and semantic information on trajectory pattern are stored as STTs. Let us consider a relational schema and the following relations: person(id: String, name: String) pattern(id: String, idPer String, traj: STT, day: Date) city(name: String, zone: Region ) mode(name: String) The relation person gives person names. The relation pattern gives patterns of persons idPer over a period day. The relation city describes regions and the relation mode gives transport mode names. Let us formulate the following example queries. Query 1. What is the transport mode that a person p used to accomplish its ith activity during the day d?

SELECT Mode_Of_Trip(PA.traj, Trip_Before_Activity(PA.traj, Nth_Activity(PA.traj, i))) FROM person AS PR, pattern AS PA WHERE PR.id = PA.idPers AND PA.day = d The result of this query is the transport mode of the trip occurring before the ith activity. Query 2. Which persons traversed the city c during the day d? SELECT P.name FROM person AS PR, pattern AS PA, city AS CT WHERE PR.id = PA.idPers AND PA.day = d AND PA.traj TST_Cross_Polygon CT.zone This query uses the topological predicate TST_Cross_Polygon to test whether person trajectories crossed the region describing the given city. Query 3. Which persons had the same spatio-temporal behavior as the person of id id during the day d? SELECT PR1.nom FROM person AS PR1, person AS PR2, pattern AS PA1 , pattern AS PA2 WHERE PR1.id = PA1.idPers AND PR2.id = PA2.idPers AND PR2.id = id AND PA1.day = d AND PA2.day = d AND PA1.traj TST_Equal_TST PA2.traj

5. Conclusion The database representation of spatio-temporal trajectories still requires the development of semanticbased approaches. The research presented in this paper develops an algebraic data type, named STT, for a semantic-based representation of spatio-temporal trajectories that also includes semantic, spatial, temporal and spatio-temporal operations. The potential of the approach is illustrated by several query operations. The STT data type is able to reveal additional knowledge on the dynamics, changes and evolution of the represented trajectories. Further work concerns the implementation and validation of the approach on an existing database kernel.

6. References [1] T. Hägerstrand, “What about people in regional science?”, Papers of the Regional Science Association, vol. 24, no.1, 1970, pp. 6-21.

[2] B. Lenntorp, “Paths in Space-Time Environments: A Time-Geographic Study of the Movement Possibilities of Individuals”. Lund Studies in Geography, Series B , vol. 44, 1976. [3] H. J. Miller, “A measurement theory for time geography”, Geographical Analysis, vol. 37, 2005, pp. 17-45. [4] K. Hornsby and M. J. Egenhofer, “Modeling Moving Objects Over Multiple Granularities”, Annals of Mathematics and Artificial Intelligence, vol. 36, 2002, pp. 177-94. [5] M. Erwig, R. H. Güting, M. Schneider and M. Vazirgiannis, “Spatio-Temporal Data Types: An Approach to Modelling and Querying Moving Objects in Databases”, GeoInformatica, vol. 3, no. 3, 1999, pp. 269-296. [6] R. H. Güting, M. Erwig, C. S. Jensen, N. A. Lorentzos, M. Schneider, M. Vazirgiannis, and H. Böhlen, “A foundation for representing and querying moving objects”, ACM Trans. Database Syst, vol. 25, no. 1, 2000, pp. 1-42. [7] L. Forlizzi, R. H. Güting, E. Nardelli and M.Schneider, “A Data Model and Data Structures for Moving Objects Databases”, Proc. of the 2000 ACM SIGMOD international conference on Management of data, (Dallas, Texas), 2000, pp. 319-330. [8] J.A. Cotelo Lema, L. Forlizzi, R. H. Güting, E. Nardelli, and M. Schneider, “Algorithms for Moving Object Databases”, The Computer Journal, vol 46, no. 6, 2003, pp. 680-712. [9] R.H. Güting, T. Behr, V. T. de Almeida, Z. Ding, F. Hoffmann, and M. Spiekermann, SECONDO: An Extensible DBMS Architecture and Prototype, Informatik-Report 313, Fernuniversität Hagen, 2004. [10] N. Pelekis, Y. Theodoridis, S. Vosinakis and T. Panayiotopoulos, “Hermes - A Framework for LocationBased Data Management”, Proc. of the 10th International Conference on Extending Database Technology (EDBT06), Munich, Germany, 2006, pp. 1130-1134. [11] R. Praing and M. Schneider, “A Universal Abstract Model for Future Movements of Moving Objects”, Proc. of the 10th AGILE Int. Conf. on Geographic Information Science, 2007. [12] R. H. Güting, V. T. Almeida and Z. Ding, “Modelling and querying moving objects in networks”, VLDB Journal, vol. 15, 2006, pp. 165-190. [13] V. Noyon, C. Claramunt and T. Devogele, “A relative representation of trajectories in geographical spaces”, Geoinformatica, vol. 4, no. 11, 2007, pp. 479-496. [14] S. Spaccapietra, C. Parent, M. L. Damiani, J. A. F. De Macedo, F. Porto and C. Vangenot, “A conceptual view on trajectories”, Data and Knowledge Engineering, vol. 65, 2008, pp. 126-146. [15] M. Raubal, “Representing concepts in time”, Proc. of the international conference on Spatial Cognition VI, Germany, 2008, pp. 328-343. [16] J. F. Allen, “Towards A General Theory of Action and Time”, Artificial Intelligence, vol. 23, 1984, pp. 123-154. [17] M. Egenhofer and R. G. Golledge, ed., Spatial and Temporal Reasoning in Geographic Information Systems, Oxford: Oxford University Press, 1998.