1.1 Problem statement and ontributions Moving obje t positions are aptured at a given time interval, with a ertain ated with them in the form of attributes. These geometries are denoted Pla es also alled seman ti traje tories, given that they an provide more information of Interest (PoIs). When a moving obje t spends a fair amount of time within a by Spa apietra et al. [12℄, where it is assumed that obje ts move over a map in traje tories [3, 8℄. Many re ent proposals perform this kind of analysis not over the original MOD, but over a database built based on the ideas introdu ed ertain point in time, namely the obje t was lo ated at oordinates t, Oid (x, y). that ontains disjoint geometries, and there is also semanti information asso iA very a tive resear h area in this setting is the dis overy of sequential patterns granularity. Thus, the traje tory of a moving obje t is given by samples omwhi h an be analyzed in order to obtain interesting patterns. Sin e lo ations of obje t’s traje tory as a sequen e of stops instead of a sequen e of points. Thus, gorithms appear as natural tools for querying and mining traje tory databases.
PoI, the PoI is onsidered a stop of the traje tory, and all points in the PoI (x, y) by means of ele troni devi es (e.g., GPS, RFID), produ ing traje tory data, a moving obje t are reported as a time-ordered sequen e, sequential pattern alsequential pattern analysis an be applied to this approximation of traje tories, posed of a nite number of tuples of the form stating that at a < Oid, x, y, t >, than the one provided by the points alone. x, y, t are repla ed by a data obje t representing a stop. This allows onsidering ea h addressed so far. Here we study this problem and provide a solution, building where an item is a tuple omposed of an obje t identier, a time instant, and a knowledge, the problem of nding sequential patterns that a ounts for the harpla e of interest These patterns an be used during the sequential pattern [5℄4. requirements, are not of interest to the user [2℄.
Gmez et al. re ently introdu ed RE-SPaM, a language that an express framework. Piet-QL is an SQL-like query language that an express omplex and Piet data model [4℄, a proposal aimed at integrating GIS and OLAP in a single powerful spatial and OLAP queries, and supports the operators in luded in the terms of the (temporal and non-temporal) attributes of the items to be analyzed, Open Geospatial Consortium spe i ation 6 for SQL. In addition, it in orporates over previous work in the elds of SOLAP and sequential pattern mining.
Several authors have emphasized the need of dis overing patterns in traje tories
mining pro ess to prune sequen es that, although satisfying minimum support
In order to retrieve spatial data, we need a query language that an return
sequential patterns by means of regular expressions over onstraints dened in
spatial obje ts. For this, we use Piet-QL a language that supports the [6℄5,
at dieren t temporal and/or spatial granularities. However, to the best of our
a teristi s of the geographi environment in whi h the obje ts move has not been
[8℄ propose to obtain patterns over so- alled importan t pla es (a region where a
expressions allow dening more omplex patterns, intensionally. The idea of
on the notion of pla es of interest. Giannotti et.al. introdu ed t-patterns, for
of the languages involved in our proposal. Se tion 3 introdu es the RE-SPaM++
For instan e, it annot deal with time onstraints or ategories, neither supports
of interest [5℄, resulting in the RE-SPaM language, dis ussed in Se tion 2.
using regular expressions for traje tory analysis was rst proposed by Mouza and
1.2 Related work
Rigaux [1℄. They present a language based on regular expressions for querying
Some re ent proposals address the problem of mining patterns in MODs, based
that these patterns are basi ally dened by extension. On the ontrary, regular
Railway Station > Castle Square > Museum. Karli and Saygin
a variable ( x). In this language, ea h o urren e of a variable in the pattern is
mining on regions of [3℄. A t-pattern is of the form sequential1hp1a0tmteinrns in2the1r5emstin
this language using regular expressions to express sequential patterns over pla es
The remainder of the paper is organized as follows. Se tion 2 gives an overview
mobility patterns where ea h zone is represented by its label (a onstant) or by
pattern mining algorithm is modied to allow an e ien t implementation of our
ideas. We on lude in Se tion 6.
tra ed obje t spends a fair amount of time) at dieren t time granularities. Note
variables or data des ribing the geographi environment. Gmez et al. extend
query language and provides examples. Se tion 4 des ribes how the sequential
instantiated with the same value. The language, however, has some limitations.
1. There are two moving obje ts, and and the table ontains only the O1 O2,
with the identiers of the level members in the OLAP dimension (in the example
keyword GIS tells that the query returns spatial obje ts. The query ontains a
airports and tourist attra tions. Ea h ategory s hema is omposed of a set of
tourist appli ation in ludes four ategory s hemas, namely hotels, restaurants,
FROM [Sales℄
malized instan e of the ToI orresponding to the ategory instan es of Figure
an item is des ribed by its initial and nal instants, and denoted [ts, tf℄. A pair
filter([Store℄.[Store Distri t℄.Members,
respond
As an example, a pattern expressing traje tories of tourists who visit hotel oering heap pri es), at the same part of the day (e.g., both of them during the attribute pri e with a literal, and returns ‘equal’, ‘less’, or ‘greater than’; the rst parameter is an attribute of the ategory o urren es of restaurants and H1 and then a pla e hara terized as ‘ heap’ or that serves Fren h food, reads: pressions, en losed between squared bra kets. The regular expression language is built in the usual way, supporting the standard operators ?’,‘.’,‘|’). (‘()’,‘*’,‘+’,‘ morning) on O tober 10th, 2008 uses this fun tion, reading: also returns a literal. For example, a fun tion ompares the compares(price, c), Synta ti ally, the rst parameter may be an attribute of a ategory o urren e R3 (Figure 1). Pla es that serve Fren h food are R1 and R2. During the mining to return ranges of time for a temporal attribute of an item (e.g., ‘Early MornThe disjun tion is evaluated as follows: ‘ heap’ pla es are restaurants R1 and ing’, ‘Morning’,..). The query T raje tories that visit two pla es (the se ond one voked as Also rollup fun tions la OLAP an be dened compares (price,‘100’). ‘ onstant’, and fun tionName(attr, ...) = variable, and an be dened ad-ho . tourist attra tions, and the se ond one is a onstant. The fun tion an be inof expli it enumeration of all the possibilities. extension is very simple: we only add a WITH statement to a Piet-QL SELECT or ‘false’, and it is invoked as We now give some containedBy(geom, r.geom). geometri onditions to be in luded in the patterns. We present RE-SPaM , a also programs omprising sequen es of Piet-QL and RE-SPaM statements. returns a ursor over tuples (i.e., a set of literals), not a literal. Thus, we need language that integrates Piet-QL and RE-SPaM allowing to add SOLAP ondiThe fun tion returns a literal. parameter must be of the form a.b, where the semanti s is that b is the name The kinds of fun tions dis ussed in Se tion 2 are not enough to support of the geometries in the ursor dened by r.geom. The fun tion returns ‘true’ geom (e.g., the geometry of the PoI in our running example) is ontained by any lause. This statement generates a sort of materialized view that is used in a WITH TABLE regRiver(the_geom) AS examples that illustrate the use of RE-SPaM++.
SELECT GIS DISTINCT(bel_regn.the_geom) Q1. Traje tories that stop at a pla e whi h belongs to a region that ontains a tions to onstraints in the regular expressions of RE-SPaM. Synta ti ally, this geometri onditions in regular expression-based onstraints. A Piet-QL query RE-SPaM expression. Thus, the language allows not only single statements but of an attribute, and a is the name of a table asso iated to some WITH lause. rst parameter whi h orresponds to an attribute of a ategory o urren e (for rivers, in a stru ture named r.geom (using the WITH lause), we an then use river, and whose next stop is an airport or a tourist attra tion.
WHERE ontains(bel_regn.the_geom,bel_river.the_geom); example, geom) or a temporal attribute (ts, tf, or their sub-parts). The se ond Sin e moving obje ts evolve in a geographi environment, we would like to +al+low FROM bel_regn, bel_river this result to dene a fun tion that he ks whether the value of the attribute For example, if a Piet-QL query returns the geometries of regions rossed by to dene new kinds of fun tions. The syntax for these fun tions onsists in a ∧ short _distance(geom, ++ shows the initial and nal states of In the nal phase of the rst step (the C1.
H2 is dis arded sin e it an not satisfy any path of length one in the automaton. step with is analyzed against the ToI to he k for minimum support. k = 1), C1 out if ‘pol3’, ‘pol4’ and ‘pol5’ are ontained in some tuple of the ursor reThus, all sequen es ontaining H2 are pruned. Analogously, the system nds gRiver.the_geom, by taking advantage of the ma ro and mi ro a hes. Figure 4 at the expense of algorithm exe ution times.
We have presented a language that allows to in lude spatial OLAP queries in regular expressions that are used during sequential pattern mining for pruning when dealing with sequential patterns in traje tory databases, and, to the best sequen es that are of no interest to the user. We believe this is a relevant feature of our knowledge, no proposal of this kind has been introdu ed so far in the eld.
Our experimental results show that this language enhan ement is not a hieved