Online discovery of co-movement patterns in mobility data

ABSTRACT

The advent of GPS technologies generates location data-streams and accentuates the importance of developing practical tools that can process and analyze the vast amounts of location data at a given moment in a meaningful way. Profiling the trajectory of a moving object with respect to the trajectories of its surrounding objects, for example, can elicit its mobility behaviour and analyze it in order to inform domain experts with critical knowledge in real time. For instance, clustering multiple moving objects with respect to their spatial and temporal dimension to identify co-movement patterns. In this paper, we propose a novel graph-based online co-movement pattern mining algorithm, called EvolvingClusters, which can be used to discover different collective movement behaviours (like the well-known flocks and convoys) in a unified way based on the activity of multiple concurrent objects through time and space. We evaluate EvolvingClusters using real-world and synthetic datasets from multiple mobility domains. Our study demonstrates the effectiveness of the proposed algorithm as well as its value towards a tool to profile semantically rich behaviour and with capabilities to observe and categorize multiple moving objects in real-time.

KEYWORDS:

• Data analytics
• semantic enrichment
• collective movement behaviour
• co-movement patterns
• evolving clusters

Acknowledgments

This work was partially supported by projects i4Sea (grant T1EDK-03268) and Track&Know (grant agreement No 780754), which have received funding by the European Regional Development Fund of the EU and Greek national funds (through the Operational Program Competitiveness, Entrepreneurship and Innovation, under the call Research-Create-Innovate) and the EU Horizon 2020 R&I Programme, respectively.

Data and codes availability statement

The data and codes that support the findings of this study are available at https://doi.org/10.6084/m9.figshare.11918715.

Disclosure statement

No potential conflict of interest was reported by the author(s).

Notes

1. In this paper, we use the linear interpolation/extrapolation models. Other models, e.g. polynomial, spline, etc., can be used as well but their assessment is beyond our scope.

2. https://en.wikipedia.org/wiki/Ball_treeBall Tree, From Wikipedia the free encyclopedia.

3. https://scikit-learn.org/stable/modules/generated/sklearn.neighbors.BallTree.html#sklearn.neighbors.BallTreeBallTree, scikit-learn Documentation.

4. The dataset is publicly available at https://zenodo.org/record/1167595#.XjSPOcYzaV5zenodo.org.

5. The dataset is publicly available at http://chorochronos.datastories.org/?q=content/flightaware-ads-b-march-2017chorochronos.datastories.org.

6. The dataset is publicly available at https://research.microsoft.com/en-us/downloads/b16d359d-d164-469e-9fd4-daa38f2b2e13/research.microsoft.com

7. The dataset is publicly available at https://www.kaggle.com/c/pkdd-15-taxi-trip-time-prediction-iikaggle.com

8. https://en.wikipedia.org/wiki/Separation_(aeronautics)Separation (aeronautics) – From Wikipedia, the free encyclopedia

9. https://en.wikipedia.org/wiki/Lane#Lane_widthLane width (urban transportation) – From Wikipedia, the free encyclopedia

10. https://www.anaconda.com/

11. https://okeanos-knossos.grnet.gr/home/

12. ‘Moving Flock Finder’ is publicly available at https://kdd.isti.cnr.it/moflock-moving-flock-finderkdd.isti.cnr.it

13. The dataset is publicly available at https://kdd.isti.cnr.it/moflock-moving-flock-finderkdd.isti.cnr.it

Additional information

Notes on contributors

Andreas Tritsarolis

Andreas Tritsarolis is a graduate (2020) of the Department of Informatics, University of Piraeus, currently studying Data Science and Machine Learning at M.Sc. level. He also participates as a junior researcher in the Data Science Lab of the University of Piraeus, collaborating in a number of research projects. His research interests lie in the areas of Data Science for Mobility Data, as well as Machine Learning, with emphasis on Deep Learning Architectures. He has co-authored a paper in conference proceedings and a journal article, both in the field of Mobility Data Analytics.

George-Stylianos Theodoropoulos

George-Stylianos Theodoropoulos is a graduate (2020) of the Department of Informatics, University of Piraeus, currently studying Big Data Analytics at MSc level. He also participates as a junior researcher in the Data Science Lab of the University of Piraeus, collaborating in a number of research projects. His research interests include Data science for mobility data, Data clustering, Database management and Machine Learning. He has co-authored a paper in conference proceedings and a journal article, both in the field of Mobility Data Analytics.

Yannis Theodoridis

Dr. Yannis Theodoridis is Professor of Data Science with the Department of Informatics, University of Piraeus, Greece. He has participated on several boards, including the editorial board of ACM Computing Surveys (2016-19) and the Endowment of the Symposium on Spatial and Temporal Databases - SSTD (2010-). He has also served as general co-chair for SSTD'03 and ECML/PKDD'11, PC vice-chair for IEEE ICDM'08, and PC member for several conferences, including ACM SIGMOD/PODS, IEEE ICDE, ACM SIGKDD, IEEE ICDM, etc. Since 2001, he has been a (co-) principal investigator in several research projects funded by various government agencies (EU, Greece) through open calls. His research interests include Data Science (big data management & analytics) for humans’ mobility-related information. He has co-authored three monographs and over 100 refereed articles in scientific journals and conferences, with over 11,000 citations (h=49), according to Google Scholar.