Abstract
The collective motion of a set of moving entities like people, birds, or other animals, is characterized by groups arising, merging, splitting, and ending. Given the trajectories of these entities, we define and model a structure that captures all of such changes using the Reeb graph, a concept from topology. The trajectory grouping structure has three natural parameters, namely group size, group duration, and entity inter-distance. These parameters allow us to obtain detailed or global views of the data. We prove complexity bounds on the maximum number of maximal groups that can be present, and give algorithms to compute the grouping structure efficiently. Furthermore, we showcase the results of experiments using data generated by the NetLogo flocking model and from the Starkey project. Although there is no ground truth for the groups in this data, the experiments show that the trajectory grouping structure is plausible and has the desired effects when changing the essential parameters. Our research provides the first complete study of trajectory group evolvement, including combinatorial, algorithmic, and experimental results.
MB, BS & FS are supported by the Netherlands’ Organisation for Scientific Research (NWO) under project no. 612.001.106, 639.022.707 & 612.001.022, respectively.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Benkert, M., Gudmundsson, J., Hübner, F., Wolle, T.: Reporting flock patterns. Computational Geometry 41(3), 111–125 (2008)
Biasotti, S., Giorgi, D., Spagnuolo, M., Falcidieno, B.: Reeb graphs for shape analysis and applications. Theor. Comput. Sci. 392(1-3), 5–22 (2008)
Buchin, K., Buchin, M., van Kreveld, M.J., Speckmann, B., Staals, F.: Trajectory grouping structures. CoRR, abs/1303.6127 (2013)
Dey, T.K., Wang, Y.: Reeb graphs: approximation and persistence. In: Proc. 27th ACM Symp. on Computational Geometry, pp. 226–235 (2011)
Edelsbrunner, H., Harer, J., Mascarenhas, A., Pascucci, V., Snoeyink, J.: Time-varying Reeb graphs for continuous space-time data. Computational Geometry 41(3), 149–166 (2008)
Edelsbrunner, H., Harer, J.L.: Computational Topology – an introduction. American Mathematical Society (2010)
Ester, M., Kriegel, H., Sander, J., Xu, X.: A density-based algorithm for discovering clusters in large spatial databases with noise. In: Proc. 2nd International Conference Knowledge Discovery and Data Mining, vol. 1996, pp. 226–231. AAAI Press (1996)
Fomenko, A., Kunii, T. (eds.): Topological Methods for Visualization. Springer, Tokyo (1997)
Gudmundsson, J., van Kreveld, M.: Computing longest duration flocks in trajectory data. In: Proc. 14th ACM International Symposium on Advances in Geographic Information Systems, GIS 2006, pp. 35–42. ACM (2006)
Gudmundsson, J., van Kreveld, M., Speckmann, B.: Efficient detection of patterns in 2D trajectories of moving points. GeoInformatica 11, 195–215 (2007)
Huang, Y., Chen, C., Dong, P.: Modeling herds and their evolvements from trajectory data. In: Cova, T.J., Miller, H.J., Beard, K., Frank, A.U., Goodchild, M.F. (eds.) GIScience 2008. LNCS, vol. 5266, pp. 90–105. Springer, Heidelberg (2008)
Jeung, H., Yiu, M.L., Zhou, X., Jensen, C.S., Shen, H.T.: Discovery of convoys in trajectory databases. PVLDB 1, 1068–1080 (2008)
Kalnis, P., Mamoulis, N., Bakiras, S.: On discovering moving clusters in spatio-temporal data. In: Medeiros, C.B., Egenhofer, M., Bertino, E. (eds.) SSTD 2005. LNCS, vol. 3633, pp. 364–381. Springer, Heidelberg (2005)
Li, Z., Ding, B., Han, J., Kays, R.: Swarm: Mining relaxed temporal moving object clusters. PVLDB 3(1), 723–734 (2010)
Oregon Department of Fish and Wildlife and the USDA Forest Service. The Starkey project (2004)
Parsa, S.: A deterministic O(m logm) time algorithm for the Reeb graph. In: Proc. 28th ACM Symp. on Computational Geometry, pp. 269–276 (2012)
Sleator, D.D., Tarjan, R.E.: A data structure for dynamic trees. Journal of Computer and System Sciences 26(3), 362–391 (1983)
Sumpter, D.: Collective Animal Behavior. Princeton University Press (2010)
Vieira, M.R., Bakalov, P., Tsotras, V.J.: On-line discovery of flock patterns in spatio-temporal data. In: Proc. 17th ACM International Conference on Advances in Geographic Information Systems, GIS 2009, pp. 286–295. ACM (2009)
Wang, Y., Lim, E.-P., Hwang, S.-Y.: Efficient algorithms for mining maximal valid groups. The VLDB Journal 17(3), 515–535 (2008)
Wilensky, U.: NetLogo flocking model. Center for Connected Learning and Computer-Based Modeling. Northwestern University, Evanston, IL (1998)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Buchin, K., Buchin, M., van Kreveld, M., Speckmann, B., Staals, F. (2013). Trajectory Grouping Structure. In: Dehne, F., Solis-Oba, R., Sack, JR. (eds) Algorithms and Data Structures. WADS 2013. Lecture Notes in Computer Science, vol 8037. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-40104-6_19
Download citation
DOI: https://doi.org/10.1007/978-3-642-40104-6_19
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-40103-9
Online ISBN: 978-3-642-40104-6
eBook Packages: Computer ScienceComputer Science (R0)