A Problem of Detecting Stops While Tracking Moving Objects Under the Stream Processing Regime
DOI:
https://doi.org/10.26636/jtit.2023.4.1481Keywords:
stream processing, object tracking, GPS monitoring, physical activity monitoring, algorithm complexityAbstract
The tracking of moving objects with the use of GPS/GNSS or other techniques is relied upon in numerous applications, from health monitoring and physical activity support, to social investigations to detection of fraud in transportation. While monitoring movement, a common subtask consists in determining the object's moving periods, and its immobility periods. In this paper, we isolate the mathematical problem of automatic detection of a stop of tracking objects under the stream processing regime (ideal data processing algorithm regime) in which one is allowed to use only a constant amount of memory, while the stream of GNSS positions of the tracked object increases in size. We propose an approximation scheme of the stop detection problem based on the fuzziness in the approximation of noise level related to the position reported by GNSS. We provide a solving algorithm that determines some upper bounds for the problem's complexity. We also provide an experimental illustration of the problem at hand.
Downloads
References
A. Domin, D. Spruijt-Metz, D. Theisen, Y. Ouzzahra, and C. Vogele, "Smartphone-based Interventions for Physical Activity Promotion: Scoping Review of the Evidence over the Last 10 Years", JMIR mHealth uHealth, vol. 9, no. 7, pp. 638-648, 2021.
View in Google Scholar
Y. Ye, Y. Zheng, Y. Chen, J. Feng, and X. Xie, "Mining Individual Life Pattern Based on Location History", in: Tenth International Conference on Mobile Data Management: Systems, Services and Middleware, Taipei, Taiwan, 2009.
View in Google Scholar
S.E. Wiehe et al., "Using GPS-enabled Cell Phones to Track the Travel Patterns of Adolescents", International Journal of Health Geographics, vol. 7, art. no. 22, 2008.
View in Google Scholar
S.S. Dukare, D.A. Patil, and K. Rane, "Vehicle Tracking, Monitoring and Alerting Systems: A Review", International Journal of Computer Applications, vol. 119, no. 10, pp. 39-43, 2015.
View in Google Scholar
Traccar: GPS Tracking Software - Free and Open Source System [Online]. Available: https://www.traccar.org.
View in Google Scholar
P. Deshmukh, A. Bhajibhakre, S. Gambhire, A. Channe, and N. Deshpande, "Survey of Geofencing Algorithms", International Journal of Computer Science Engineering Techniques, vol. 3 no. 2, 2018 http://www.ijcsejournal.org/volume3/issue2/IJCSE-V3I2P1.pdf.
View in Google Scholar
Y. Ge, H. Xiong, C. Liu, and Z. Zhou, "A Taxi Driving Fraud Detection System", in: 2011 IEEE 11th International Conference on Data Mining, Vancouver, Canada, pp. 181-190, 2011.
View in Google Scholar
J.B. Oliva, "Anomaly Detection and Modeling of Trajectories", M.Sc. Thesis, Carnegie Mellon University, Pittsburgh, USA, 2012 https://apps.dtic.mil/sti/citations/ADA566110.
View in Google Scholar
Y. Bu, L. Chen, A.W. Fu, and D. Liu, "Efficient Anomaly Monitoring over Moving Object Trajectory Streams" in: Proc. of 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Paris, France, 2009.
View in Google Scholar
L.H. Tran, Q.V.H. Nguyen, N.H. Do, and Y. Zhixian, "Robust and Hierarchical Stop Discovery in Sparse and Diverse Trajectories", Infoscience. EPFL. Technical Reports, 2011, https://infoscience.epfl.ch/record/175473.
View in Google Scholar
L. Killars, B. Schouten, and O. Mussmann, "Stop and Go Detection in GPS-position Data - Discussion Paper", CBS. Discussion Paper, Netherlands, 2020 https://www.researchgate.net/publication/338402776_Stop_and_Go_detection_in_GPS-position_data_-_Discussion_Paper.
View in Google Scholar
G. Cich, L. Knapen, T. Bellemans, D. Janssens, and G. Wets, "TRIP/STOP Detection in GPS Traces to Feed Prompted Recall Survey", Procedia Computer Science, vol. 52, pp. 262-269, 2015.
View in Google Scholar
H. Safi, B. Asemi, M. Mesbah, and L. Ferreira, "A Trip Detection Method for Smartphone-assisted Travel Data Collection", in: Proceedings of the Transportation Research Board (TRB) 95th Annual Meeting, Washington, USA, pp. 1-18, 2016 https://eprints.qut.edu.au/125568/.
View in Google Scholar
L. Gong, T. Yamamoto, and T. Morikawa, "Identification of Activity Stop Locations in GPS Trajectories by DBSCAN-TE Method Combined with Support Vector Machines", Transportation Research Procedia, vol. 32, no. 3, pp. 146-154, 2018.
View in Google Scholar
R. Montoliu and D. Gatica-Perez, "Discovering Human Places of Interest from Multimodal Mobile Phone Data", in: Proc. of the 9th International Conference on Mobile and Ubiquitous Multimedia, Limassol, Cyprus, 2010.
View in Google Scholar
J.H. Kang, H. Jong, W. Welbourne, B. Stewart, and G. Borriello, "Extracting Places from Traces of Locations", in: Proc. of 2nd ACM Intl Workshop on Wireless Mobile Applications and Services on WLAN Hotspots, Philadelphia, USA, pp. 110-118, 2004.
View in Google Scholar
C.E. Leiserson, R.L. Rivest, and C. Stein, Introduction to Algorithms, 2nd Edition, MIT Press, London, UK, 2001 (ISBN: 9780262032933).
View in Google Scholar
T.M.T. Do and D. Gatica-Perez, "The Places of Our Lives: Visiting Patterns and Automatic Labeling from Longitudinal Smartphone Data", IEEE Transactions on Mobile Computing, vol. 13, no. 3, pp. 638-648, 2014.
View in Google Scholar
The Open Street Map service, [Online]. Available: https://www.openstreetmap.
View in Google Scholar
Downloads
Published
Issue
Section
License
Copyright (c) 2023 Paweł Białoń
This work is licensed under a Creative Commons Attribution 4.0 International License.
