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