\section{Preliminaries} \label{sec:preliminares}

Section 3.1 presents an application scenario using trajectory data and discusses specific requirements for trajectory modeling and analysis, which we claim to be necessary for facilitating the development of those applications. Section 3.2 informally introduces basic definitions related to trajectories that will be used throughout this paper.

\subsection{Application Scenario}\label{sub:applicationscenario}

Logistic management is an important class of applications that may take advantage of analyzing trajectory data. Particularly, applications that manage truck delivery of goods are of special interest due its importance for the global economy. For this kind of application, truck travels may be used to check whether delivery plans are being correctly executed (real time analysis) or they may analyzed to assess the performance of the delivery system (historical analysis). Indeed, analyzing truck travels is the key to improve knowledge about many questions on logistic management, such as: Are the delivery plans being respected? Taking into account the current state of truck deliveries, when a customer will be visited? Is it possible to reduce the number of truck travels without compromising revenue?  Why a delivery was not performed?  The answers to such questions are key to support decision-making processes in delivery planning and routing.

In order to analyze the truck travels, hereinafter called simply truck trajectories, this application must record two types of data:

(1) Data about truck trajectories: Each truck is equipped with a controller device, which automatically collects data about the truck location and allows the truck driver to inform certain events that occurred during the travel. Data about truck position is sent at regular intervals to a central server, which stores this data in a conventional database. For example, when the truck stops, the following data is recorded: (a) the kind of stop: delivery or otherwise, (b) when the stop is not a delivery, the activities executed by the truck driver during the stop must be informed, such as: lunching, resting, refueling, emergency, etc. When the truck is traveling,  the controller device informs the speed, direction and position of the truck. In addition, data about the streets travelled by is recorded. 

(2) Data related to truck trajectories: regions of interest (e.g. district, regions, state, etc) associated with each trajectory; the list of customers visited in each trajectory; traffic conditions  associate with the trajectory (to explain delivery delays).

Examples of typical queries executed in this application scenario are:

Q1. What is the location of the truck 1103 and which were the customers it visited?

Q2. What is the number of trajectories and the corresponding average duration, carried out in the City of Sao Paulo in April?


Q3. When customer A will be visited?

\subsection{Basic Definitions}
Based on the application scenario of Section 3.1, we introduce the definitions on which the rest of the paper depends on. 

From a conceptual point of view, a trajectory must be perceived by the application or the database designer as an identifiable and manageable object. Even if the trajectory is defined as a first-class object, applications sometimes require relating information to segments of a trajectory, for example, to indicate that, in a time interval along the trajectory, the truck stopped to deliver merchandise to a customer. Thus, a conceptual view of trajectories must provide mechanisms to deal with the trajectory as a first-class object, as well as to decompose the trajectory into meaningful events.

In more detail, a geographical positioning device collects, at regular time intervals, the geographic location of a moving object (e.g. \textit{latitude}, \textit{longitude}), associated with a timestamp. Over time, the device accumulates a set of triples (e.g. \textit{lat}, \textit{long}, \textit{instant}), which represent the movement of the object. However, the sequence of triples collected may in fact represent different trajectories of the moving object. For example, suppose a truck made several trips per day. At the end of the day, the collection of triples captured by the device should be separated into different trajectories, each one representing a different trip. By contrast, suppose that the same set of triples should be used by a truck maintenance application. In this second scenario, the trajectory of the truck should be defined as the sequence of all triples collected throughout the day. Thus, in general, the definition of what is a trajectory depends on the application, that is, the definition of the start and the end points of a trajectory depend on how the application perceives the movement of the object.

Therefore, the designer should provide a function to segment the raw data collected by the positioning device and to generate trajectories, which will then be stored in a database and manipulated by the application. In the literature, the process of segmenting raw trajectory data is known as \textit{semantic construction} of the trajectories (hence the term \textit{semantic trajectories} we adopt). This may also include other tasks, such as the correction of points collected by the positioning device.


To capture such concepts, we introduce a sequence of definitions. A \textit{spatio-temporal point} is a triple $p=(l,g,t)$, where $l$ and $g$ are real numbers that represent latitude and longitude, respectively, and $t$ is a positive real number representing a timestamp.


%
%A \textit{raw spatio-temporal dataset} is a sequence of spatio-temporal points. Note a raw spatio-temporal dataset has no semantics.
%
%Let $A$ be an \textit{event attribute}, taking values from the domain $D$. An $event$ over $A$ is a triple $e=(s,d,a)$, where $s$ and $d$ are positive real numbers such that $s \le d$, representing the $begin$ and $end times$ of $e$, and $a$ is an attribute value from $D$, representing the \textit{event information}.
%
%A \textit{semantic trajectory} over a set of event types $T$ is a triple $s=(s,d,L)$, where $s$ and $d$ are positive real numbers such that $s \le d$, representing the begin and end times of $s$, and $L=(e_{1},...,e_{n})$ is a finite sequence of events over $A$ such that: (i) the begin and end time of $e_{i}$ lie in the interval $[s,d]$, for $i=[1,n]$; and (ii) the start time of $e_{i+1}$ is greater than or equal to the end time of $e_{i}$, for $i=[1,n)$. 
%
%To summarize, a semantic trajectory is an application-defined representation of the evolution of the position of a moving object (perceived as a point) during a given time interval. The application may extract (or define) semantic trajectories from a raw spatio-temporal dataset using a function which incorporates the semantics of what a trajectory for the domain should be. The definition of a semantic trajectory includes a sequence of events, which can be referenced and managed individually. The application may in fact treat events as first-class objects that carry additional semantics.

%-------- NOVA DEFINICAO DO CASANOVA COM REDUNDANCIA -------------

A \textit{raw spatio-temporal dataset} is a finite sequence of spatio-temporal points $R=((l_{1},g_{1}, t_{1}),...,$ $(l_{k}, g_{k}, t_{k}))$ such that, for all $i \in [1,k)$, $t_{i} < t_{i+1}$. Note a raw spatio-temporal dataset has no semantics.

Let $A$ be an \textit{event attribute}, taking values from the domain $D$. An $event$ over $A$ is a triple $e=(b,d,a)$, where $b=(l_{b},g_{b},t_{b})$ and $d=(m_{d},h_{d},u_{d})$ are points such that $t_{b} \le u_{d}$, representing the $begin$ and \textit{end points} of $e$, and $a$ is an attribute value from $D$, representing the \textit{event information}.  A \textit{semantic trajectory} over an event attribute $A$ is a quadruple $s=(b,d,R,L)$, where 
\begin{itemize}
	\item $b=(l_{b},g_{b},t_{b})$ and $d=(m_{d},h_{d},u_{d})$ are points such that $t_{b} \le u_{d}$, representing the $begin$ and \textit{end points} of $s$;
%	\item $R=((l_{1},g_{1},t_{1}),...,(l_{k},g_{k},t_{k}))$ is a raw spatio-temporal dataset such that $t_{b}=t_{1}$ and $t_{d}=t_{k}$;
	\item $R=((l_{1},g_{1},t_{1}),...,(l_{k},g_{k},t_{k}))$ is a raw spatio-temporal dataset such that $b$ and $d$, the begin and end points of $s$, are the first and the last points of $R$;
	\item $L=(e_{1},...,e_{n})$ is a finite sequence of events over $A$ such that: 
      \begin{itemize}
            \item for $i=[1,n]$, the begin and end points of $e_{i}$ are points in $R$; 
            \item for $i=[1,n)$, if $d_{i}=(m_{i},h_{i},u_{i})$ is the end point of $e_{i}$ and $b_{i+1}=(l_{i+1},g_{i+1},t_{i+1})$ is the begin point of $e_{i+1}$, then $u_{i} \le t_{i+1}$.
      \end{itemize}
\end{itemize}



Note that $b$ and $d$, the begin and end points of $s$, are just a definitional convenience, since they can be trivially deduced from $R$.

To summarize, a semantic trajectory is an application-defined representation of the evolution of the position of a moving object (perceived as a point) during a given time interval. The application may extract (or define) semantic trajectories from a raw spatio-temporal dataset using a function which incorporates the semantics of what a trajectory for the domain should be. The definition of a semantic trajectory includes a sequence of events, which can be referenced and managed individually. The application may in fact treat events as first-class objects that carry additional semantics.


