Abstract
Group pattern mining based on spatio-temporal trajectories have gained significant attentions due to the prevalence of location-acquisition devices and tracking technologies. Representative work includes convoy, swarm, travelling companion, gathering, and platoon. However, these works based on Euclidean space cannot handle group pattern discovery in non-planar space, such as urban road networks. In this paper, we propose a new group pattern, named converging, and its mining method in road networks. Unlike the aforementioned group patterns, a converging indicates that a group of moving objects converge from different directions for a certain time period. Motivated by this, we formalize the concept of a converging based on cluster containment relationship. Since the process of discovering convergings over large scale road network constrained trajectories is quite lengthy, we propose a density clustering algorithm based on road networks (DCRN) and a cluster containment join (CCJ) algorithm to improve the performance. Specifically, DCRN adopts the well-known filter-refinement-verification framework for efficiently identifying core points, which utilizes the upper bound property for \(\varepsilon \)-neighbourhood of point set on an edge to dramatically reduce the candidate core points. To process the neighbourhood queries efficiently, we further develop a vertex-neighbourhood based index, which precomputes the \(\varepsilon \)-neighbourhoods of all vertices, to facilitate neighbourhood queries of all points in road networks. In addition, to process the CCJ efficiently, we develop a signature tree based on road network partition index to organize the clusters in road networks hierarchically, which enable us to prune enormous unqualified candidates in an efficient way. Finally, extensive experiments with real and synthetic datasets show that our proposed methods achieve superior performance and good scalability.
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
Similar content being viewed by others
References
Orakzai, F., Calders, T., Pedersen, T.B.: k/2-hop: Fast mining of convoy patterns with effective pruning. PVLDB 12(9), 948–960 (2019)
Li, Z., Ding, B., Han, J., Kays, R.: Swarm: mining relaxed temporal moving object clusters. PVLDB 3(1), 723–734 (2010)
Tang, L., et al.: On discovery of traveling companions from streaming trajectories. In: ICDE 2012, pp. 186–197 (2012)
Zheng, K., Zheng, Y., Yuan, J., Shang, S.: On discovery of gathering patterns from trajectories. In: ICDE 2013, pp. 242–253 (2013)
Li, Y., Bailey, J., Kulik, L.: Efficient mining of platoon patterns in trajectory databases. DKE 100, 167–187 (2015)
Fan, Q., Zhang, D., Wu, H., Tan, K.: A general and parallel platform for mining co-movement patterns over large-scale trajectories. PVLDB 10(4), 313–324 (2016)
Chen, L., Gao, Y., Fang, Z., Miao, X., Jensen, C.S., Guo, C.: Real-time distributed co-movement pattern detection on streaming trajectories. PVLDB 12(10), 1208–1220 (2019)
Ester, M., Kriegel, H., Sander, J., Xu, X.: A density-based algorithm for discovering clusters in large spatial databases with noise. In: SIGKDD 1996, pp. 226–231 (1996)
Zhong, R., Li, G., Tan, K., Zhou, L., Gong, Z.: G-tree: an efficient and scalable index for spatial search on road networks. TKDE 27(8), 2175–2189 (2015)
Li, Z., Chen, L., Wang, Y.: G*-tree: an efficient spatial index on road networks. In: ICDE 2019, pp. 268–279 (2019)
Shen, B., et al.: V-Tree: efficient kNN search on moving objects with road-network constraints. In: ICDE 2017, pp. 609–620 (2017)
Karypis, G., Kumar, V.: Multilevel k-way partitioning scheme for irregular graphs. JPDC 48(1), 96–129 (1998)
Yiu, M.L., Mamoulis, N.: Clustering objects on a spatial network. In: SIGMOD 2004, pp. 443–454 (2004)
Chen, J., Lai, C., Meng, X., Xu, J., Hu, H.: Clustering moving objects in spatial networks. In: Kotagiri, R., Krishna, P.R., Mohania, M., Nantajeewarawat, E. (eds.) DASFAA 2007. LNCS, vol. 4443, pp. 611–623. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-71703-4_52
Papadias, D., Zhang, J., Mamoulis, N., Tao, Y.: Query processing in spatial network database. VLDB 2003, 802–813 (2003)
Sun, W., Chen, C., Zheng, B., Chen, C., Liu, P.: An air index for spatial query processing in road networks. TKDE 27(2), 382–395 (2015)
Lee, K.C.K., Lee, W., Zheng, B., Tian, Y.: ROAD: a new spatial object search framework for road networks. TKDE 24(3), 547–560 (2012)
Acknowledgement
This study was supported by NSFC41971343, NSFC61702271, NSF of Jiangsu Province BK20200725 and the Postgraduate Research Innovation Program of Jiangsu Province KYCX201258.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 Springer Nature Switzerland AG
About this paper
Cite this paper
Jia, J., Hu, Y., Zhao, B., Ji, G., Liu, R. (2021). Discovering Collective Converging Groups of Large Scale Moving Objects in Road Networks. In: Jensen, C.S., et al. Database Systems for Advanced Applications. DASFAA 2021. Lecture Notes in Computer Science(), vol 12682. Springer, Cham. https://doi.org/10.1007/978-3-030-73197-7_21
Download citation
DOI: https://doi.org/10.1007/978-3-030-73197-7_21
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-73196-0
Online ISBN: 978-3-030-73197-7
eBook Packages: Computer ScienceComputer Science (R0)