Affiliations: [a] Instituto Tecnológico de Buenos Aires, Buenos Aires, Argentina | [b] Department of Computer and Decision Engineering (CoDE) CP 165/15, Université Libre de Bruxelles, Bruxelles, Belgium
Correspondence:
[*]
Corresponding author: Alejandro A. Vaisman, Department of Computer Decision Engineering (CoDE) CP 165/15, Université Libre de Bruxelles, 50 Av. Roosevelt, B-1050, Bruxelles, Belgium. Tel.: +32 2 650 27 53; Fax: +32 2 650 47 13; E-mail: avaisman@ulb.ac.be.
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 pre-defined 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 application-relevant 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 RE-SPaM, that can intensionally express sequential patterns. The constraints in RE-SPaM 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 RE-SPaM expression. This makes the task of the analyst easier, and the mining algorithm more efficient. We also show that RE-SPaM 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 RE-SPaM+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.
