

L. I. GÃ³mez and A. Vaisman. Mining Semantic Trajectories. Intelligent Data Analysis, 2012.
Abstract
A typical problem in the field of moving object (MO) databases consists in discovering interesting trajectory patterns. To solve this problem, data mining techniques are commonly used. Due to the huge volume of these trajectory data, some form of compression facilitates the data processing. One of such compression techniques is based on the notion of stops and moves. In this approach, a set of places that are relevant to the application, denoted Places of Interest (POIs) is selected. If a moving object spends a predefined amount of time in a place of interest, this place is considered a stop for the object's trajectory. Thus, raw trajectories given by (Oid, t, x,y)tuples can be replaced by a sequence of applicationrelevant stops. This leads to the concept of semantic trajectory, in short, a trajectory obtained by replacing raw trajectory data with a sequence of stops, and enriched with metadata of the POIs corresponding to such stops. We present a language based on regular expressions over constraints, denoted RESPaM, that can intensionally express sequential patterns. The constraints in RESPaM are defined as conjunctions of equalities over metadata of the POIs. In addition, we introduce a data mining algorithm, based on sequential pattern mining techniques, where uninteresting sequences are pruned in advance making use of the automaton that accepts a RESPaM expression. This makes the task of the analyst easier, and the mining algorithm more efficient. We also show that RESPaM can be extended to support spatial functions, thus integrating spatial data in a moving object setting (proposals so far only account for the MO trajectories themselves). We denote the resulting language RESPaM+S. We show that the overhead of this extension is negligible, due to caching techniques that we explain in the paper. We close the paper with a case study over which we perform experiments to study the main variables that impact the performance of the mining algorithm.




