Trajectory Data Analysis
Tracking of moving entities has become ubiquitous due to technologies like GPS, RFID, and video, and large collections of trajectory data have been formed. These concern data on pedestrians, vehicles, sports players, hurricanes and animals, to name just a few. Applications range from security and ecology to soccer player movement analysis and weather forecasting. The collections allow any type of spatio-temporal data analysis like clustering, segmentation, group detection, popular region discovery, and so on.
Research at the division Virtual Worlds has concentrated on efficient geometric algorithms for the analysis of trajectory data. We formalize generic patterns or structures that may contain knowledge, and use these to design and analyse algorithms. Two of the key data analysis types are segmentation and group detection. In segmentation, we attempt to partition a trajectory into meaningful parts by using geometric measures like speed, heading, and curvature. In group detection we formalize groups as subsets of moving entities that are spatially close, that stay close for a sufficiently long period, and that consist of sufficiently many entities. The resulting three-parameter model captures groups in moving entities quite well.
Additional details and video material can be found here.
|Maike Buchin, Anne Driemel, Marc van Kreveld, Vera Sacristán: Segmenting trajectories: A framework and algorithms using spatiotemporal criteria. J. Spatial Information Science 3(1): 33-63 (2011)|
|Boris Aronov, Anne Driemel, Marc van Kreveld, Maarten Löffler, Frank Staals: Segmentation of Trajectories for Non-Monotone Criteria. ACM Transactions on Algorithms (TALG) 12(2): December 2015. Issue-in-Progress, Article No. 26, ACM New York, NY, USA, doi 10.1145/2660772|
|Kevin Buchin, Maike Buchin, Marc van Kreveld, Bettina Speckmann, Frank Staals: Trajectory Grouping Structure. Journal of Computational Geometry 6(1): 75-98 (2015).|
|Irina Kostitsyna, Marc van Kreveld, Maarten Löffler, Bettina Speckmann, Frank Staals: Trajectory Grouping Structure under Geodesic Distance. Symposium on Computational Geometry 2015: 674-688|