=Paper=
{{Paper
|id=None
|storemode=property
|title=Efficient Mobility Pattern Stream Matching on Mobile Devices
|pdfUrl=https://ceur-ws.org/Vol-960/paper5.pdf
|volume=Vol-960
}}
==Efficient Mobility Pattern Stream Matching on Mobile Devices==
https://ceur-ws.org/Vol-960/paper5.pdf
Efficient Mobility Pattern Stream
Matching on Mobile Devices
Simona-Claudia Florescu1 and Michael Mock1 and Christine Körner1 and Michael May1
Abstract. The increasing amount of mobile phones that are and time constraints are applied to complete patterns. For achiev-
equipped with localization technology offers a great opportunity for ing an efficient implementation on the mobile device, we spread the
the collection of mobility data. This data can be used for detecting task of pattern matching over a filter hierarchy that is fed with the
mobility patterns. Matching mobility patterns in streams of spatio- stream of GPS input data: Firstly, a VisitEventFilter detects whether
temporal events implies a trade-off between efficiency and pattern a certain location is being visited and, if so, forwards a visit event to a
complexity. Existing work deals either with low expressive patterns, PatternFilter, which can handle arbitrary regular expressions (includ-
which can be evaluated efficiently, or with very complex patterns ing Kleene closure) over visit events. Lastly, a TimeConstraintFilter
on powerful machines. We propose an approach which solves the is used to check any expression over the travel time for the com-
trade-off and is able to match flexible and sufficiently complex pat- plete pattern. By this approach, we can use standard deterministic
terns while delivering a good performance on a resource-constrained automatons for implementing matching of regular expressions and
mobile device. The supported patterns include full regular expres- can perform efficient time constraint checking in constant time. The
sions as well as relative and absolute time constraints. We present remainder of this paper is structured as follows: in the next section,
the definition of our pattern language and the implementation and we present our approach, mobility pattern matching over streams
performance evaluation of the pattern matching on a mobile device, containing the pattern definition language and details of the imple-
using a hierarchy of filters which continuously process the GPS input mentation of the pattern matching algorithm. Section 3 contains the
stream. performance and scalability evaluation and Section 4 discusses re-
lated work. The last section, conclusions, provides a short summary,
improvement suggestions and future work.
1 INTRODUCTION
The analysis of mobility behavior based on GPS-tracks has become
a popular field of research [15, 7, 4, 16, 18]. In the context of the
2 MOBILITY PATTERN MATCHING
European LIFT [10] project, we aim at the on-line monitoring of Figure 1 describes our general approach for building local and global
global non-linear phenomena from massively distributed streams of mobility models. As described in [11], our mobility model is based
data. In the mobility domain such global phenomena are, for exam- on counts of occurrences of events, whereby an event represents the
ple, mass events or changes in traffic flows. The basic approach of occurrence of a specific predefined spatio-temporal behavior in the
LIFT technology for the reduction of communication overhead is to observed GPS track. The local mobility model represents the behav-
build local mobility models on each device and to communicate only ior of a specific user and is locally computed on the device itself,
significant changes to a central coordinator, which is computing the whereas the global model is build by aggregating all local models
global model. This paper presents an approach for building the local on a single node (global coordinator). LIFT technology is used to
mobility model efficiently on a mobile device. reduce the amount of communication needed for maintaining the
Mobility patterns such as used in [4] and [7] are an appropriate global model correct over time. The basic approach thereby is to de-
way of modeling spatio-temporal mobility behavior. Powerful spe- fine a so-called SafeZone, in which the local model can safely vary
cialized database systems such as [16] allow to retrieve patterns from without notifying the global coordinator [17]. In this paper, we fo-
spatio-temporal data using complex pattern queries, in which spa- cus on the question whether the input for generating the local model
tial and temporal conditions can be freely combined. Providing this can be computed efficiently on a mobile device, i.e., the gray shaded
flexibility for pattern definitions for building local mobility models part in Figure 1. Being able to compute a model locally is a prerequi-
on a mobile device would surely exceed the computational power site for applying LIFT technology for communication reduction. The
of such devices. Patterns expressed by regular expressions only, but local mobility model is computed by processing the stream of GPS
not supporting queries over travel times (as in [4]) might have a bet- updates as provided by an Android Location Provider through a hier-
ter chance of being efficiently implemented on a mobile device. The archy of filters (see [8] for the details of filter interface definitions).
same holds for the work of [7], which allows queries over travel times At the first level, the VisitEventFilter detects whether the device stays
but supports sequential patterns only. Our approach of building mo- for a pre-defined minimum time in one of the pre-defined locations,
bility models is based on the notion of visits as being formally intro- which are stored in the local location database. If so, a visit event
duced in [12, 11]. Patterns are build as regular expression over visits, is generated, which will be processed at the next layer in the hier-
1 Fraunhofer Institute for Intelligent Analysis and Information
archy, the PatternFilter. This Filter takes list of predefined patterns
Systems, Germany, email:simona.florescu@gmail.com, first- (regular expressions over visits) as input and matches the incoming
name.lastname@iais.fraunhofer.de visit events against these patterns. In case of a match, a pattern event
23
is forwarded to the next filter. At the last filter level, the TimeCon-
visitEvent := (id, type, entryT ime, exitT ime) (2)
straintFilter, the time constraints for the matched pattern are vali-
dated. If they are fulfilled, the respective pattern frequency count is We define a visitExpression as being the concatenation of the id,
increased. The input for our implementation consists therefore of: type and the stayTime using the within separator ”,”:
(1) an infinite stream of GPS-sensed location updates, (2) a given set
of interesting locations to be monitored, (3) a set of patterns with the
set of interesting locations as domain, as depicted in the figure below, visitExpression := concat(id, type, stayT ime, sep = ”, ”)
Figure 1. (3)
The stay time is the difference between the exit and entry time.
Similarly to [4] it is expressed as a sequence of repeated time units t
so that it can be matched by regular expressions. This enables pattern
Mobile Device with Android OS LIFT Global queries like ”a stay time of at least 5 and at most 20 minutes”. The
Coordinator duration of a time unit depends on the required accuracy and can be
LIFT
LIFT Local
Local Mobility
Mobility Model
Model Change notification
set to e.g. one minute. An example of a visit expression is: 1,01,tttt
Global
Matched TimePattern which represents a visit event with location 1, of type 01 (here code
Mobility
TimeConstraintFilter
Model
for cinema) and a stay time of 4 time units.
A pattern consists of (1) a regular expression of one or several
PatternEvent
Pattern & visitExpressions and (2) a timeConstraint - containing absolute and
TimeConstra
int Definition
PatternFilter
relative constraints:
VisitEvent
VisitEventFilter
pattern := (regex(visitExpression+), timeConstraint) (4)
Location
GPS Update
Definition
Database
Android
Android Location
Location Provider
Provider
timeConstraint := ([fexit ], [opf ], [lentry ], [opl ], [lc], [rc]) (5)
The regular expression is defined according to the regular
language specified in [14] on the alphabet of visitExpressions
(Definition 3). Several expressions are hereby separated by a
Figure 1. Filter hierarchy and data flow of the approach.
semicolon. In a digital format we represent a pattern in XML
(Extended-Markup-Language). Figure 2 shows an example of a
mobility pattern. The pattern’s XML representation is shown in the
code snippet below Figure 2. The part of the pattern containing the
regular expression is
2.1 Pattern Matching Language 1,01,t{0,4};@;2,02,t{4,8};
We propose a pattern language based on regular expressions. We
It denotes a visit to location 1 (of type 01) for up to 4 time units
define the language for the three main levels of our approach: Vis-
followed by an arbitrary number of visits to unspecified locations
itEventFilter, PatternFilter and TimeConstraintFilter.
(expressed by @3 ), followed by a visit to location 2 (of type 02) for
Firstly, we define a location, of which the input data for the Vis-
a stay time between 4 and 8 time units.
itEventFilter consists. A location is defined by an id, a type, a spatial
The time constraint of the pattern definition (Definition 5) is
extend and the minimum stay time at the location. Note that this def-
checked by the TimeConstraintFilter and contains absolute and rel-
inition allows for overlapping locations (for example: a location for
ative constraints. The absolute time constraints are: (1) fexit - the
a specific attraction inside the location ”Amusement Park”) as well
constraint on the first event exit time in milliseconds; (2) opf - the
as for monitoring complete regions by dividing a region in a spa-
operator applied to fexit with the following possible values: 0 for
tial grid of locations. In our implementation we consider rectangular
less, 1 for equals, 2 for greater than, - for none; (3) lentry - the con-
spatial shapes, therefore we define the four coordinates of the bound-
straint on the last event entry time in milliseconds and (4) opl - the
ing boxes. The id is a unique identification for the location and the
operator applied to lentry with the same values as opf . In the ex-
type of location (e.g. cinema, fast-food, school) is coded for short-
ample given below no absolute time constraints are specified but, for
ness purposes with two digits. The minimum stay time defines the
example, the values: fexit = 1, 000, 000 and op1 = 2 would im-
time period that an encounter with a location must last in order to
pose on the first visit event that its exitTime must be greater than
become a visit.2 A location is defined as:
1,000,000. The relative time constraints are: (5) lc - the left con-
straint for the pattern duration in milliseconds and (6) rc - the right
location := id, type, xmin , xmax , ymin , ymax , minStay (1) constraint for the whole pattern in milliseconds e.g. lc < lentry −
fexit < rc. For the given example the relative time constraint is:
We represent a visit event, generated by the VisitEventFilter with 0 < visitEventid=2 .entryT ime − visitEventid=1 .exitT ime <
the following attributes: location identification, location type, entry 7, 200, 000.
and exit time (in milliseconds): Below, the XML for the pattern depicted in Figure 2 is shown
containing the pattern id, the regular expression of the sequence of
2 Both the bounding box radius and minimum stay time are defined visits as well as the time constraints.
application-depend, depending on the location type (e.g. for bigger loca-
tions we set the minimum stay time higher) in order to distinguish between 3 In [14] the JAVA library automaton specifies a regular language implemen-
passing by and visiting. tation where the symbol ’@’ represents any sequence of characters
24
In the PatternFilter we model the patterns using deterministic fi-
nite automata [9]. We instantiate an automaton for each of the parsed
<2h patterns from the XML input. In the PatternMatcher class we create
and model automata using the JAVA library automaton [14] to match
the regular expressions specified in the first part of Definition 4.
2 The class structure of the pattern matching algorithm consists of:
1
• A PatternFilter class, which instantiates in its constructor a list of
PatternMatcher objects by calling the PatternReader class. The
PatternFilter maintains the list of all patterns. It receives visit
events in its update function and generates and forwards pattern
events to the next filter, the TimeConstraintFilter.
Figure 2. Mobility pattern example: a visit to location 1 followed by an • A PatternMatcher class where an automaton is modeled. In the
arbitrary number of visits to intermediate locations followed by a visit to constructor the variables needed for saving the automaton data
location 2 with a maximum time period of 2 hours (7,200,000 milliseconds) structure are initialized as well as a pattern event object for storing
between the first and last visit the information of the matched pattern.
• The PatternReader reads and converts a pattern from XML to an
object of type PatternMatcher.
• The filter class TimeConstraintFilter checks if the time constraints
1
1,01,t{0,4};@;2,02,t{4,8}; are fulfilled for a received pattern event. In its constructor, it reads
and parses the time constraints for each pattern into a TimeCon-
-
-
-
straint object.
-
0
7200000
In the PatternMatcher constructor, provided in the pseudocode of
Class 1, the field automaton represents an object of type Ru-
nAutomaton, defined in the JAVA library automaton. The fields
for defining the state of the automaton are actualState and
isInitial. The patternEvent is an object of type Event
which stores the properties of the generated pattern event for each
2.2 Pattern Matching Algorithm
match. The logic of the PatternMatcher is contained in the func-
Our approach consists of several filters implemented in an embed- tions processVisit and reset shown in the pseudocode of Class 1.
ded Android application: a VisitEventFilter, a PatternFilter and the The processVisit function receives a visitEvent as a pa-
TimeConstraintFilter which return a pattern distribution from a GPS rameter, generated by the previous filter (the VisitEventFilter), and
stream input, see Figure 1 and Section 1. returns a boolean value of true if the visit event completes the
The first filter, the VisitEventFilter, receives as input the stream matching of a given pattern and false if not. The processVisit func-
of GPS coordinates and a set of locations stored in a local SQLite tion generates the visitExpression which has the structure
database and generates visit events. In order to do so it checks given in Definition 3. The stepThrough function runs through
whether there is a spatial match between the coordinates and the automaton with each character from the visitExpression
the input of locations, described in Section 2.1 Pattern Matching as transition and returns the step obtained after the run. A value
Language. The input database contains the tables, which are joined for step of -1 means that the matching failed. Any other value
by their id: means that the automaton advances in another state, changing vari-
able actualState. In this case and if the isInitial was true,
Locations1(id, xmin , ymin , ymax , ymax ) the patternEvent stores the exitTime of the visit event. If the
Locations2(id, latitude, longitude, name, type, min stay) visitExpression could not be matched, the function reset is
called. There, the patternEvent attributes are set to null and the
The main steps of the visit filtering approach are: firstly, the state of the automaton is set to initial. Another check in the function
database is queried to retrieve the ids of the locations in which the is whether the automaton has reached the final state. In this case
current position is in. As we are restricting the current implementa- the patternEvent stores the entryTime of the visit event since
tion to rectangular locations, this can be achieved by a first query this is its last visit event matched in the pattern.
such as: The pseudocode of the PatternFilter is shown in Class 2. In the
constructor a list of PatternMatcher objects is generated, one for
SELECT Id FROM Locations1 WHERE x ≥ xmin and each given pattern. Further, the PatternReader class, which reads and
x ≤ xmax and y ≥ ymin and y ≤ ymax parses the XML input patterns, is called. For each pattern string the
PatternReader instantiates a PatternMatcher by calling its construc-
followed by another query on the Locations2 table for retrieving tor as shown in Class 1. In the update function of the PatternFilter,
the rest of the location information (Definition 1). for each new visit event update, all the existing PatternMatcher ob-
Secondly, we are maintaining a list of entered locations. Whenever jects from the patternMatcherList are traversed and called to
we detect that the current GPS point is no longer in a specific one of execute the processVisit function, shown in Class 1. If the re-
those entered locations, we check whether we have been staying at turned value from processVisit is true, then the matched pattern
least a time of minStay within that location and, if so, generate a visit event, patternEvent is forwarded to the next filter.
event for that location. In any case, the location is removed from the Finally, in the TimeConstraintFilter the matched pattern time con-
list of entered locations. The complete algorithm can be found in [6]. straints are checked, if any are provided. The time constraints are de-
25
Class 1 PATTERN M ATCHER patterns possess time constraints. Our artificial GPS data is generated
Fields: automaton - deterministic automaton for the pattern such that 40% of all points lead to a match with the location database
actualState - the actual state of the automaton and generate a visitEvent. For performance evaluations of the Pat-
patternEvent - an Event object for a matched pattern
isInitial - boolean value for initial state of automaton ternFilter 2,6% of the input visitEvents complete a pattern match.
Constructor: P atternM atcher(id, regex) Finally, each pattern match is checked in the TimeConstraintFilter.
id - pattern id
regex - regular expression #Locations 10 100 1K 10K 100K 500K 800K
1: this.patternEvent.id ← id Run-time (ms) 0.72 0.69 0.79 0.82 0.75 0.73 0.75
2: this.automaton ← new RunAutomaton(regex) Stddev run 0.90 0.71 0.71 0.81 0.78 0.66 0.79
// using DFA java library from [14] DBQuery (ms) 0.35 0.33 0.39 0.42 0.35 0.37 0.36
3: this.reset() Stddev DBQuery 0.60 0.46 0.54 0.67 0.38 0.54 0.55
reset()
4: this.patternEvent.entryT ime ← null
5: this.patternEvent.exitT ime ← null Table 1. The run-time values for the VisitEventFilter.
6: this.actualState ← (this.automaton.getInitialState())
7: this.isInitial ← true
boolean processVisit(visitEvent)
8: visitExpression ← makeV isitExpression(visitEvent) #Patterns 100 1K 10K 100K 300K
9: step ← automaton.stepT hrough(actualState, visitExpression) Run-time (ms) 1.2 17.1 157.0 1498.4 4397.3
// stepThrough returns the state reached by inputting all characters of the visitEx- Stddev. 0.08 6.5 7.1 24.0 129.6
pression to the automaton starting with actualState Start-up (ms) 266.3 275.1 239.2 499.9 1341.8
10: if step 6= −1 then // step is -1 for a mismatch Stddev. 201.6 225.1 48.2 9.3 15.3
11: if this.automaton.isInitial then
12: this.patternEvent.entryT ime ← visitEvent.exitT ime Heap size (MB) 2.67 2.68 2.75 2.76 2.76
13: this.isInitial ← f alse Memory (MB) 5 10 10 12 24
14: end if
15: actualState ← step
16: else // the visitExpression could not be entirely matched
17: this.reset()
Table 2. The run-time values for the PatternFilter
18: end if
// check whether the automaton has reached the end state
19: if automaton.isF inal() then
20: this.patternEvent.exitT ime ← visitEvent.entryT ime
21: this.reset() Firstly, we measured the run-time for the VisitEventFilter. We var-
// automaton is set on the initial state and all variables are reinitialized ied the size of the location set from 10 to 800,000. Table 1 shows the
22: return true
23: else obtained performance results. We distinguish between the database
24: return f alse
25: end if query (DBQuery) and the entire run-time (Run-time) measured be-
fore forwarding a visit event, therefore the DBQuery run-time is in-
Class 2 PATTERN F ILTER cluded in the run-time value. Table 1 shows that the run-time of the
Fields: patternM atcherList - a list of objects of type VisitEventFilter is nearly constant when varying the number of loca-
PatternMatcher tions in the underlying database. We ascribe this behavior to caching
Constructor: P atternF ilter() effects in the SQLite database, taking into account that the database
1: reader = newP atternReader() is opened only once and that all queries are read-only. Ongoing ex-
2: this.patternM atcherList ← reader.parseAutomaton(input f ile) periments and code analysis showed that the time needed for the
// instantiate list of P atternM atcher
database part in the VisitEventFilter depends on the number of over-
update(visitEvent)
3: for P atternM atcher ∈ patternM atcherList do
lapping locations in which a given GPS point resides. In the syn-
4: if P atternM atcher.processV isit(visitEvent) then thetic GPS tracks used in the evaluation, the GPS points match to
5: f orward(P atternM atcher.patternEvent) one (non-overlapping) location only. All visit events are detected in
6: end if
7: end for a time well below one second, which is the time difference between
two GPS location updates in worst case. In addition, the number of
fined in Section 2.1 (Pattern Matching Language) and relate to the monitored locations will be geographically limited in practice. For
first and last event in the matched pattern, respectively. The Time- example, when restricting the collected POI (points-of-interest) to
ConstraintFilter constructor instantiates a TimeConstraint object for the city of Cologne, we obtained a set of about 20,000 locations.
each pattern. When invoked with a pattern id of the incoming pattern Secondly, we evaluated the run-time of the PatternFilter under
event, it checks the existing time constraints for the respective pattern an increasing number of checked patterns with an average match-
id. The generated event at this level is a matched time pattern. ing percentage of 2,6%. The results are shown in Table 2. The table
also contains the reading and parsing time for all patterns (Start-up),
which takes place in the PatternFilter constructor. The run-time for
3 PERFORMANCE EVALUATION
the pattern matching increases linearly with the number of tested pat-
Our performance evaluation for checking the potential of the appli- terns (Run-time), which corresponds to the main loop executed in the
cation in practice is based on synthetic data. The tests were run on PatternFilter.update method. Furthermore, for each of the instances
a Samsung Galaxy SII GT-I9100, operating Android Gingerbread, of the PatternFilter we show the heap size and the allocated mem-
version 2.3.3. The GPS stream data consists of synthetically gener- ory. The values were captured for about three runs as delivered by the
ated coordinates. In addition, we retrieved 800,000 points of interest Android debugger class. The results for the heap size are relatively
(POI) from the geo-service OSM [13] for the location set. The POIs constant and show for the memory allocations fair results, since the
were obtained for Germany and are of 15 different types. The gener- high number of 300,000 patterns use about 24MB out of 64MB.
ated patterns are formulated similarly to the example pattern in Sec- The TimeConstraintFilter has a constant run-time, since it only
tion 2.1 and Figure 2, i.e. they specify the first and last location and retrieves the time constraints for the respective pattern id from a
allow an arbitrary number of visit events in between. In addition, all HashMap, and the time constraint validation is trivial. The run-time
26
for the TimeConstraintFilter is approximately 10 milliseconds per we can apply optimizations from the area of complex event process-
pattern event. ing, see [5]. Furthermore, the handling of travel times (in addition
to pattern time constraints) will be investigated by the repeated hier-
archical composition of our PatternFilter and TimeConstraint filters.
4 RELATED WORK Lastly, we will evaluate the performance of our approach on real-
Table 3 gives an overview on related work in the field of spatio- world data collected from 70 users in the city of Cologne, Germany.
temporal mobility analysis. The criteria on which we compare re-
lated work are: (1) stay time (Stay) - patterns with conditions on
ACKNOWLEDGEMENTS
minimum and maximum stay time, (2) travel time (TT) - the time
span between two locations in the pattern, (3) the time constraints The research leading to these results has received funding from the
(TC) - time constraints on the full pattern, i.e. on first and last loca- European Union’s Seventh Framework Programme (FP7/2007-2013)
tion in the pattern, (4) full regular expressions (FullRE) - supporting under grant agreement no. 255951 (LIFT Project).
all the expression options from regular expressions i.e. Kleene clo-
sure (+,*), negation, conjunction, disjunction, and (5) predicates -
REFERENCES
additional complex conditions on the pattern (e.g. an attribute should
have an incrementing value) and (6) Stream - whether the approach [1] J. Agrawal, Y. Diao, D. Gyllstrom, and N. Immerman, ‘Efficient pat-
tern matching over event streams’, in Proc. of the 2008 ACM SIGMOD
is applied on-line (on stream data) or later, off-line. Although our international conference on Management of data, SIGMOD ’08, pp.
matched patterns are not the most complex, our approach is the first 147–160, New York, NY, USA, (2008). ACM.
one successfully tested on a resource-constrained device. [2] A. Demers, J. Gehrke, B. Panda, M. Riedewald, V. Sharma, and
W. White, ‘Cayuga : A General Purpose Event Monitoring System’,
Approach Stay TT TC FullRE Pred. Stream Publish, 412–422, (2007).
T-patterns [7] - X - - - - [3] Android developer website. www.developer.android.com, Last ac-
Mob. patterns [4] X - - X - - cessed: April 2012.
SASE [18] X - X X X X [4] C. du Mouza and P. Rigaux, ‘Mobility patterns’, GeoInformatica, 9(4),
SASE+ [1] X - - X X X 297–319, (2005).
Cayuga [2] - - X X X X [5] O. Etzion and P. Niblett, Event Processing in Action, Manning Publica-
tions Company, 2010.
STPQ [16] X X X X X -
[6] S.-C. Florescu, ‘Efficient retrieval of mobility patterns on mobile de-
Our Approach X - X X - X
vices’, RWTH Aachen, Germany, (August 2012). To be submitted.
[7] F. Giannotti, M. Nanni, F. Pinelli, and D. Pedreschi, ‘Trajectory pattern
mining’, in Proc. of the 13th ACM SIGKDD international conference
Table 3. Comparison with related work on Knowledge discovery and data mining, KDD ’07, pp. 330–339, New
York, NY, USA, (2007). ACM.
[8] M. Hoffmann, ‘A simulation environment for distributed stream analy-
sis’, Master Thesis, Univ. of Appl. Sc. Bonn-Rhein-Sieg, (2011).
The function addProximityAlert provided by the Android [9] J. E. Hopcroft and J. D. Ullman, Introduction to Automata Theory, Lan-
guages, and Computation, volume 2, Addison-Wesley, 1979.
LocationManager [3] performs a similar task as our VisitEvent- [10] LIFT (Using Local Inference in Massively Distributed Systems).
Filter. Comparative experiments between both classes showed that http://www.lift-eu.org.
the Android function can register proximity alerts for only less than [11] C. Körner, Modeling Visit Potential of Geographic Locations Based on
30,000 locations, compared to our approach, which has been tested Mobility Data, Phd thesis, University of Bonn, 2012.
for up to 800,000 locations. [12] C. Körner, D. Hecker, M. May, and S. Wrobel, ‘Visit potential: A com-
mon vocabulary for the analysis of entity-location interactions in mo-
bility applications’, in Geospatial Thinking, Lecture Notes in Geoinfor-
mation and Cartography, 79–95, Springer, (2010).
5 CONCLUSION [13] Open Street Maps. www.osm.org, Last accessed: December 2011.
In this paper we have shown that the detection of state-of-the art com- [14] A. Møller. dk.brics.automaton – finite-state automata and regular ex-
pressions for Java, 2010. http://www.brics.dk/automaton/.
plex mobility patterns can be implemented on a resource-constrained [15] D. J. Patterson, L. Liao, K. Gajos, M. Collier, N. Livic, K. Olson,
environment such as a mobile device. Our experiments show that the S. Wang, D. Fox, and H. Kautz, ‘Opportunity knocks: a system to pro-
pattern matching can process the matching of 800,000 locations and vide cognitive assistance with transportation services’, in Ubicomp, pp.
up to 10,000 complex patterns in much less than one second. For 433–450, (2004).
[16] M. A. Sakr and R. Hartmut Güting, ‘Spatiotemporal pattern queries’,
handling more locations or more patterns, measures can be taken
GeoInformatica, 15(3), 497–540, (2011).
to reduce the number of GPS position updates by configuring the [17] I. Sharfman, A. Schuster, and D. Keren, ‘A geometric approach to mon-
Android Location Provider appropriately or by adding intermediate itoring threshold functions over distributed data streams’, in Proc. of the
GPS smoothing filters. For example, for a frequency of 5 seconds per 2006 ACM SIGMOD international conference on Management of data,
position update request, our application can efficiently scale up to at SIGMOD ’06, pp. 301–312, New York, NY, USA, (2006). ACM.
[18] E. Wu, ‘High-performance complex event processing over streams’, in
least 800,000 locations and over 300,000 complex patterns. Proc. of the 2006 ACM SIGMOD international conference on Manage-
We consider a few improvements for future work. We have ini- ment of data, SIGMOD ’06, pp. 407–418, (2006).
tial measurements of battery consumption which are promising, but
need to be investigated in detail. The VisitEventFilter performs very
fast (see Table 1). This results from using rectangular locations only,
which allows to search for locations with the simple query shown in
Section 2.2 efficiently. Specific applications may, however, require
more complex location geometries. For the PatternFilter, run-times
mainly depend of the loop executed over the set of patterns. Here, we
can explore parallelism of the underlying multi-core hardware and
27