Nicolas Markey

Résumé

The popularization of geographical position devices (e.g. GPS) creates new opportunities for analyzing behavior of moving objects. However, such analysis are hindered by a lack of semantic information associated to the basic information provided by GPS. Previous works propose semantic enrichment of trajectories. Through the semantic enrichment, we could check which trajectories have a given moving sequence in an application. Often, this sequence is expressed according to the semantic application, using the approach of semantic trajectories proposed in the literature. This trajectory can be represented as a sequence of predicates that holds in some time interval. However, the solutions for querying moving sequence proposed by previous works have a high computational cost. In this paper, we propose an expressive query language to semantic trajectories that allows temporal constraints. To evaluate a query we will use model checking based on timed automata, that can be performed in polynomial time. As this model checking algorithm is not implemented yet, we propose to use UPPAAL tool, that can be more expensive theoretically, but we expected that will be ecient for our approach. In addition, we will present a query example that demonstrates the expressive power of our language. Although in this paper we will focus on semantic trajectories data, our approach is general enough for being applied to other purposes.

@inproceedings{sbbd2012-SVMM,
  author =              {Sim{\~o}es{ }De{~}Sousa, Diego V. and Viana,
                         Henrique and Markey, Nicolas and de Mac{\^e}do, Jose
                         Ant{\^o}nio F.},
  title =               {Querying Trajectories through Model Checking based
                         on Timed Automata},
  editor =              {Casanova, Marco A.},
  booktitle =           {{P}roceedings of the 27th {B}razilian {S}ymposium on
                         {D}atabases ({SBBD}'12)},
  acronym =             {{SBBD}'12},
  publisher =           {Sociedade Brasileira de Computa{\c c}{\~a}o},
  pages =               {33-40},
  year =                {2012},
  month =               oct,
  abstract =            {The popularization of geographical position devices
                         (e.g.~GPS) creates new opportunities for analyzing
                         behavior of moving objects. However, such analysis
                         are hindered by a lack of semantic information
                         associated to the basic information provided by~GPS.
                         Previous works propose semantic enrichment of
                         trajectories. Through the semantic enrichment,
                         we~could check which trajectories have a given
                         moving sequence in an application. Often,
                         this~sequence is expressed according to the semantic
                         application, using the approach of semantic
                         trajectories proposed in the literature.
                         This~trajectory can be represented as a sequence of
                         predicates that holds in some time interval.
                         However, the solutions for querying moving sequence
                         proposed by previous works have a high computational
                         cost. In~this paper, we~propose an expressive query
                         language to semantic trajectories that allows
                         temporal constraints. To~evaluate a query we will
                         use model checking based on timed automata, that can
                         be performed in polynomial time. As~this model
                         checking algorithm is not implemented yet, we
                         propose to use UPPAAL tool, that can be more
                         expensive theoretically, but we expected that will
                         be ecient for our approach. In addition, we will
                         present a query example that demonstrates the
                         expressive power of our language. Although in this
                         paper we will focus on semantic trajectories data,
                         our approach is general enough for being applied to
                         other purposes.},
}