Abstract
DBSCAN, a density-based clustering algorithm, has been widely used in pattern recognition and data mining. However, under large-scale streaming data scenarios, it suffers heavy computational cost because it examines distances between each points multiple times, especially in traffic applications which usually require calculating road network shortest distance instead of Euclidean distance. Therefore, the performance of DBSCAN for real-time clustering analyses is has become a bottleneck in such applications. Focusing on fast identifying traffic-related events, this paper utilizes linear feature to improve the efficiency of clustering by introducing linear referencing system (LRS). LRS has long been used in managing linear features, which could simplify shortest-path computation into 1-dimensional relative distance calculation, thus can significantly reduce computational complexity and cost, and meet the real-time analysis requirement of streaming data. Using vehicle GPS trajectory as an example, this study designs a LRS and its associated dynamic segmentation method for identifying traffic congestions. Experiment results proved the flexibility and efficiency of the proposed LRS-based clustering approach in identifying traffic congestions.
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
Ester, M., Keigel, H., Sander, J., Xu, X.: A density-based algorithm for discovering clusters in large spatial databases with noise. In: Proceedings of the Second International Conference on Knowledge Discovery and Data Mining (KDD) (1996)
Elnekave, S., Last, M., Maimon, O.: Incremental clustering of mobile objects. In: IEEE 23rd International Conference on Data Engineering, Istanbul (2007)
Lubr, S., Lazarescu, M.: Incremental clustering of dynamic data streams using connectivity based representative points. Data Knowl. Eng. 68(1), 1–27 (2009)
Wang, Y., Lim, E.P., Hwang, S.Y.: Efficient mining of group patterns from user movement data. Data Knowl. Eng. 57, 240–282 (2006)
Ma, S., Tang, S., Yang, D., Wang, T., Yang, C.: Incremental maintenance of discovered mobile user maximal moving sequential patterns. In: Lee, Y., Li, J., Whang, K.-Y., Lee, D. (eds.) DASFAA 2004. LNCS, vol. 2973, pp. 824–830. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-24571-1_72
Zhang, T., Ramakrishnan, R., Livny, M.: BRICH: an efficient data clustering method for very large database. In: International Conference on Management of Data (SIGMOD), New York, USA (1996)
Li, Z., Lee, J.-G., Li, X., Han, J.: Incremental clustering for trajectories. In: Kitagawa, H., Ishikawa, Y., Li, Q., Watanabe, C. (eds.) DASFAA 2010. LNCS, vol. 5982, pp. 32–46. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-12098-5_3
Nasraoui, O., Uribe, C.C., Coronel, C.R., Gonzalez, F.: TECNO-STREAMS: tracking evolving clusters in noisy data streams with a scalable immune system learning model. In: IEEE International Conference on Data Mining, Washington, USA (2003)
Park, N.H., Lee, W.S.: Cell trees: an adaptive synopsis structure for clustering multi-dimensional on-line data streams. Data Knowl. Eng. 63(2), 528–549 (2007)
Choo, J., Jiamthapthaksin, R., Chen, C., Celepcikay, O., Giusti, C., Eick, C.: MOSAIC: a proximity graph approach for agglomerative clustering. In: Song, I.Y., Eder, J., Nguyen, T.M. (eds.) DaWaK 2007. LNCS, vol. 4654, pp. 231–240. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-74553-2_21
ESRI: ArcGIS Resource. rescources.argis.com/en/help/main/10.1/index.heml#/003900000001000000. Accessed 24 Aug 2015
OpenLR. https://www.openlr.org/introduction.html. Accessed 10 Oct 2015
Acknowledgments
This work is supported by China NSFC (41671387, 2018YFB2100704, and 41171348).
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
Zhuang, Y., Ma, CL., Xie, JY., Li, ZR., Yue, Y. (2021). A Fast Clustering Approach for Identifying Traffic Congestions. In: Meng, X., Xie, X., Yue, Y., Ding, Z. (eds) Spatial Data and Intelligence. SpatialDI 2020. Lecture Notes in Computer Science(), vol 12567. Springer, Cham. https://doi.org/10.1007/978-3-030-69873-7_1
Download citation
DOI: https://doi.org/10.1007/978-3-030-69873-7_1
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-69872-0
Online ISBN: 978-3-030-69873-7
eBook Packages: Computer ScienceComputer Science (R0)