Efficient Detection of Patterns in 2D Trajectories of Moving Points

Authors: Gudmundsson, Joachim¹; Kreveld, Marc²; Speckmann, Bettina³

Source: GeoInformatica, Volume 11, Number 2, June 2007 , pp. 195-215(21)

Publisher: Springer

Buy & download fulltext article:

Price: $47.00 plus tax (Refund Policy)

Abstract:

Moving point object data can be analyzed through the discovery of patterns in trajectories. We consider the computational efficiency of detecting four such spatio-temporal patterns, namely flock, leadership, convergence, and encounter, as defined by Laube et al., Finding REMO—detecting relative motion patterns in geospatial lifelines, 201-214, (2004). These patterns are large enough subgroups of the moving point objects that exhibit similar movement in the sense of direction, heading for the same location, and/or proximity. By the use of techniques from computational geometry, including approximation algorithms, we improve the running time bounds of existing algorithms to detect these patterns.

Keywords: computational geometry; motion patterns; tracking data; approximation algorithms; data mining

Document Type: Research article

DOI: http://dx.doi.org/10.1007/s10707-006-0002-z

Affiliations: 1: Email: joachim.gudmundsson@nicta.com.au 2: Email: marc@cs.uu.nl 3: Email: speckman@win.tue.nl

Publication date: 2007-06-01