{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,12]],"date-time":"2026-05-12T23:04:12Z","timestamp":1778627052176,"version":"3.51.4"},"reference-count":33,"publisher":"MDPI AG","issue":"1","license":[{"start":{"date-parts":[[2016,12,22]],"date-time":"2016-12-22T00:00:00Z","timestamp":1482364800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IJGI"],"abstract":"<jats:p>Intersections are important components of road networks, which are critical to both route planning and path optimization. Most existing methods define the intersections as locations where the road users change their moving directions and identify the intersections from GPS traces through analyzing the road users\u2019 turning behaviors. However, these methods suffer from finding an appropriate threshold for the moving direction change, leading to true intersections being undetected or spurious intersections being falsely detected. In this paper, the intersections are defined as locations that connect three or more road segments in different directions. We propose to detect the intersections under this definition by finding the common sub-tracks of the GPS traces. We first detect the Longest Common Subsequences (LCSS) between each pair of GPS traces using the dynamic programming approach. Second, we partition the longest nonconsecutive subsequences into consecutive sub-tracks. The starting and ending points of the common sub-tracks are collected as connecting points. At last, intersections are detected from the connecting points through Kernel Density Estimation (KDE). Experimental results show that our proposed method outperforms the turning point-based methods in terms of the F-score.<\/jats:p>","DOI":"10.3390\/ijgi6010001","type":"journal-article","created":{"date-parts":[[2016,12,22]],"date-time":"2016-12-22T09:48:53Z","timestamp":1482400133000},"page":"1","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":31,"title":["Detecting Road Intersections from GPS Traces Using Longest Common Subsequence Algorithm"],"prefix":"10.3390","volume":"6","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5764-6257","authenticated-orcid":false,"given":"Xingzhe","family":"Xie","sequence":"first","affiliation":[{"name":"imec-IPI-UGent, Ghent University, Sint-Pietersnieuwstraat 41, 9000 Ghent, Belgium"}]},{"given":"Wenzhi","family":"Liao","sequence":"additional","affiliation":[{"name":"imec-IPI-UGent, Ghent University, Sint-Pietersnieuwstraat 41, 9000 Ghent, Belgium"}]},{"given":"Hamid","family":"Aghajan","sequence":"additional","affiliation":[{"name":"imec-IPI-UGent, Ghent University, Sint-Pietersnieuwstraat 41, 9000 Ghent, Belgium"},{"name":"Ambient Intelligence Research (AIR) Lab, Department of Electrical Engineering, Stanford University, Stanford, CA 94305, USA"}]},{"given":"Peter","family":"Veelaert","sequence":"additional","affiliation":[{"name":"imec-IPI-UGent, Ghent University, Sint-Pietersnieuwstraat 41, 9000 Ghent, Belgium"}]},{"given":"Wilfried","family":"Philips","sequence":"additional","affiliation":[{"name":"imec-IPI-UGent, Ghent University, Sint-Pietersnieuwstraat 41, 9000 Ghent, Belgium"}]}],"member":"1968","published-online":{"date-parts":[[2016,12,22]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Shi, W., Shen, S., and Liu, Y. (2009, January 4\u20137). Automatic generation of road network map from massive GPS, vehicle trajectories. Proceedings of the 12th International IEEE Conference on Intelligent Transportation Systems, St. Louis, MO, USA.","DOI":"10.1109\/ITSC.2009.5309871"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"601","DOI":"10.1007\/s10707-014-0222-6","article-title":"A comparison and evaluation of map construction algorithms using vehicle tracking data","volume":"19","author":"Ahmed","year":"2014","journal-title":"GeoInformatica"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"298","DOI":"10.1109\/TITS.2010.2069097","article-title":"Robust inference of principal road paths for intelligent transportation systems","volume":"12","author":"Agamennoni","year":"2011","journal-title":"IEEE Trans. Intell. Transp. Syst."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1023\/B:DAMI.0000026904.74892.89","article-title":"Mining GPS traces for map refinement","volume":"9","author":"Schroedl","year":"2004","journal-title":"Data Min. Knowl. Discov."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"61","DOI":"10.3141\/2291-08","article-title":"Inferring road maps from global positioning system traces","volume":"2291","author":"Biagioni","year":"2012","journal-title":"Transp. Res. Rec."},{"key":"ref_6","unstructured":"Edelkamp, S., and Schr\u00f6dl, S. (2003). Computer Science in Perspective, Springer."},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Cao, L., and Krumm, J. (2009, January 4\u20136). From GPS traces to a routable road map. Proceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, Washington, DC, USA.","DOI":"10.1145\/1653771.1653776"},{"key":"ref_8","unstructured":"Worrall, S., and Nebot, E. (2007, January 10\u201312). Automated process for generating digitised maps through GPS data compression. Proceedings of the Australasian Conference on Robotics and Automation, Brisbane, Australia."},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Niehoefer, B., Burda, R., Wietfeld, C., Bauer, F., and Lueert, O. (2009, January 20\u201325). GPS community map generation for enhanced routing methods based on trace-collection by mobile phones. Proceedings of the 1st International Conference on Advances in Satellite and Space Communications, Colmar, France.","DOI":"10.1109\/SPACOMM.2009.31"},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Karagiorgou, S., and Pfoser, D. (2012, January 7\u20139). On vehicle tracking data-based road network generation. Proceedings of the 20th International Conference on Advances in Geographic Information Systems, Redondo Beach, CA, USA.","DOI":"10.1145\/2424321.2424334"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1109\/MPRV.2006.83","article-title":"Scalable, distributed, real-time map generation","volume":"5","author":"Davics","year":"2006","journal-title":"IEEE Pervasive Comput."},{"key":"ref_12","unstructured":"Xie, X., Philips, W., Veelaert, P., and Aghajan, H. (2014, January 8\u201311). Road network inference from GPS traces using DTW algorithm. Proceedings of the 17th IEEE International Conference on Intelligent Transportation Systems, Qingdao, China."},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Zheng, Y., Zhang, L., Xie, X., and Ma, W.Y. (2009, January 20\u201324). Mining interesting locations and travel sequences from GPS trajectories. Proceedings of the 18th International Conference on World Wide Web, Madrid, Spain.","DOI":"10.1145\/1526709.1526816"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1080\/17489725.2014.963180","article-title":"Transit tomography using probabilistic time geography: Planning routes without a road map","volume":"8","author":"You","year":"2014","journal-title":"J. Locat. Based Serv."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1016\/j.trc.2005.04.007","article-title":"Optimized and meta-optimized neural networks for short-term traffic flow prediction: A genetic approach","volume":"13","author":"Vlahogianni","year":"2005","journal-title":"Transp. Res. Part C"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"568","DOI":"10.1016\/j.trc.2009.10.006","article-title":"Evaluation of traffic data obtained via GPS-enabled mobile phones: The Mobile Century field experiment","volume":"18","author":"Herrera","year":"2010","journal-title":"Transp. Res. Part C"},{"key":"ref_17","unstructured":"Xie, X., Wong, K., Aghajan, H., and Philips, W. (2013, January 14). Analyzing cyclists\u2019 behaviors and exploring the environments from cycling tracks. Proceedings of the Cycling Data Challenge 2013 Workshop, Leuven, Belgium."},{"key":"ref_18","unstructured":"Syberfeldt, A., and Persson, L. (2009, January 1\u20133). Using heuristic search for initiating the genetic population in simulation-based optimization of vehicle routing problems. Proceedings of the Industrial Simulation Conference 2009, Loughborough, UK."},{"key":"ref_19","unstructured":"Xie, X., Wong, K., Aghajan, H., and Philips, W. (2013, January 23\u201325). Smart route recommendations based on historical GPS trajectories and weather information. Proceedings of the Mobile Ghent, 2013, Ghent, Belgium."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"2959","DOI":"10.4304\/jcp.8.11.2959-2965","article-title":"Detecting road intersections from coarse-gained GPS traces based on clustering","volume":"8","author":"Wu","year":"2013","journal-title":"J. Comput."},{"key":"ref_21","unstructured":"Pelleg, D., and Moore, A.W. (July, January 29). X-means: Extending K-means with efficient estimation of the number of clusters. Proceedings of the Seventeenth International Conference on Machine Learning (ICML \u201900), Stanford, CA, USA."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1080\/13658816.2014.944527","article-title":"A novel approach for generating routable road maps from vehicle GPS traces","volume":"29","author":"Wang","year":"2015","journal-title":"Int. J. Geogr. Inf. Sci."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"2446","DOI":"10.3390\/ijgi4042446","article-title":"Inferring directed road networks from GPS traces by Track Alignment","volume":"4","author":"Xie","year":"2015","journal-title":"Int. J. Geo-Inf."},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Fathi, A., and Krumm, J. (2010, January 14\u201317). Detecting road intersections from GPS traces. Proceedings of the Geographic Information Science, Zurich, Switzerland.","DOI":"10.1007\/978-3-642-15300-6_5"},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Xie, X., Liao, W., Aghajan, H., Veelaert, P., and Philips, W. (2016, January 10\u201315). A novel approach for inferring intersections from GPS traces. Proceedings of the 2016 IEEE International Symposium on Geoscience and Remote Sensing, Beijing, China.","DOI":"10.1109\/IGARSS.2016.7729466"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"664","DOI":"10.1145\/322033.322044","article-title":"Algorithms for the longest common subsequence problem","volume":"24","author":"Hirschberg","year":"1977","journal-title":"J. ACM"},{"key":"ref_27","unstructured":"Denardo, E.V. (2012). Dynamic Programming: Models and Applications, Courier Corporation."},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Sniedovich, M. (2010). Dynamic Programming: Foundations and Principles, CRC Press.","DOI":"10.1201\/EBK0824740993"},{"key":"ref_29","doi-asserted-by":"crossref","unstructured":"Keogh, E.J., and Pazzani, M.J. (2001, January 5\u20137). Derivative dynamic time warping. Proceedings of the First SIAM International Conference on Data Mining (SDM\u20192001), Chicago, IL, USA.","DOI":"10.1137\/1.9781611972719.1"},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"Scott, D.W. (2015). Multivariate Density Estimation: Theory, Practice, and Visualization, John Wiley & Sons.","DOI":"10.1002\/9781118575574"},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1023\/A:1009982220290","article-title":"An evaluation of statistical approaches to text categorization","volume":"1","author":"Yang","year":"1999","journal-title":"Inf. Retr."},{"key":"ref_32","unstructured":"Liu, B. (2007). Web Data Mining, Springer."},{"key":"ref_33","unstructured":"Laboratory, B.N.S. Available online: http:\/\/bits.cs.uic.edu\/."}],"container-title":["ISPRS International Journal of Geo-Information"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2220-9964\/6\/1\/1\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T19:29:04Z","timestamp":1760210944000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2220-9964\/6\/1\/1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,12,22]]},"references-count":33,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2017,1]]}},"alternative-id":["ijgi6010001"],"URL":"https:\/\/doi.org\/10.3390\/ijgi6010001","relation":{},"ISSN":["2220-9964"],"issn-type":[{"value":"2220-9964","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,12,22]]}}}