{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,19]],"date-time":"2026-05-19T07:13:46Z","timestamp":1779174826549,"version":"3.51.4"},"reference-count":59,"publisher":"Association for Computing Machinery (ACM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2019,9,15]]},"abstract":"<jats:p>In this paper, we study the problem of large-scale trajectory data clustering,<jats:bold><jats:italic>k<\/jats:italic><\/jats:bold>-paths, which aims to efficiently identify<jats:italic>k<\/jats:italic>\"representative\" paths in a road network. Unlike traditional clustering approaches that require multiple data-dependent hyperparameters,<jats:bold><jats:italic>k<\/jats:italic><\/jats:bold>-paths can be used for visual exploration in applications such as traffic monitoring, public transit planning, and site selection. By combining map matching with an efficient intermediate representation of trajectories and a novel<jats:italic>edge-based distance<\/jats:italic>(EBD) measure, we present a scalable clustering method to solve<jats:bold><jats:italic>k<\/jats:italic><\/jats:bold>-paths. Experiments verify that we can cluster millions of taxi trajectories in less than one minute, achieving improvements of up to two orders of magnitude over state-of-the-art solutions that solve similar trajectory clustering problems.<\/jats:p>","DOI":"10.14778\/3357377.3357380","type":"journal-article","created":{"date-parts":[[2019,11,19]],"date-time":"2019-11-19T19:25:15Z","timestamp":1574191515000},"page":"29-42","source":"Crossref","is-referenced-by-count":67,"title":["Fast large-scale trajectory clustering"],"prefix":"10.14778","volume":"13","author":[{"given":"Sheng","family":"Wang","sequence":"first","affiliation":[{"name":"New York University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zhifeng","family":"Bao","sequence":"additional","affiliation":[{"name":"RMIT University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J. Shane","family":"Culpepper","sequence":"additional","affiliation":[{"name":"RMIT University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Timos","family":"Sellis","sequence":"additional","affiliation":[{"name":"Swinburne University of Technology"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xiaolin","family":"Qin","sequence":"additional","affiliation":[{"name":"Nanjing University of Aeronautics and Astronautics"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,9]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Connected cars will send 25 gigabytes of data to the cloud every hour. https:\/\/perma.cc\/BPM2--QNW4. Connected cars will send 25 gigabytes of data to the cloud every hour. https:\/\/perma.cc\/BPM2--QNW4."},{"key":"e_1_2_1_2_1","unstructured":"Guava: Google Core Libraries for Java. https:\/\/github.com\/google\/guava. Guava: Google Core Libraries for Java. https:\/\/github.com\/google\/guava."},{"key":"e_1_2_1_3_1","unstructured":"JavaFastPFOR: A simple integer compression library in Java. https:\/\/github.com\/lemire\/JavaFastPFOR. JavaFastPFOR: A simple integer compression library in Java. https:\/\/github.com\/lemire\/JavaFastPFOR."},{"key":"e_1_2_1_4_1","unstructured":"Map Matching based on GraphHopper. https:\/\/github.com\/graphhopper\/map-matching. Map Matching based on GraphHopper. https:\/\/github.com\/graphhopper\/map-matching."},{"key":"e_1_2_1_5_1","unstructured":"OpenStreetMap. https:\/\/www.openstreetmap.org. OpenStreetMap. https:\/\/www.openstreetmap.org."},{"key":"e_1_2_1_6_1","unstructured":"Repository of k-paths. https:\/\/github.com\/tgbnhy\/k-paths-clustering. Repository of k-paths. https:\/\/github.com\/tgbnhy\/k-paths-clustering."},{"key":"e_1_2_1_7_1","unstructured":"Taxi Service Trajectory Prediction Challenge 2015. http:\/\/www.geolink.pt\/ecmlpkdd2015-challenge\/. Taxi Service Trajectory Prediction Challenge 2015. http:\/\/www.geolink.pt\/ecmlpkdd2015-challenge\/."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3196959.3196972"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/VAST.2009.5332584"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/3113624.3114144"},{"key":"e_1_2_1_11_1","first-page":"1027","volume-title":"SODA","author":"Arthur D.","year":"2007","unstructured":"D. Arthur and S. Vassilvitskii . K-Means++: The advantages of careful seeding . In SODA , pages 1027 -- 1025 , 2007 . D. Arthur and S. Vassilvitskii. K-Means++: The advantages of careful seeding. In SODA, pages 1027--1025, 2007."},{"key":"e_1_2_1_12_1","first-page":"579","volume-title":"WWW","author":"Chan T.-h. H.","year":"2018","unstructured":"T.-h. H. Chan , A. Guerquin , and M. Sozio . Fully dynamic k-center clustering . In WWW , pages 579 -- 587 , 2018 . T.-h. H. Chan, A. Guerquin, and M. Sozio. Fully dynamic k-center clustering. In WWW, pages 579--587, 2018."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.14778\/3115404.3115411"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/1316689.1316758"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066157.1066213"},{"key":"e_1_2_1_16_1","first-page":"426","volume-title":"VLDB","author":"Ciaccia P.","year":"1997","unstructured":"P. Ciaccia , M. Patella , and P. Zezula . M-tree: An efficient access method for similarity search in metric spaces . In VLDB , pages 426 -- 435 , 1997 . P. Ciaccia, M. Patella, and P. Zezula. M-tree: An efficient access method for similarity search in metric spaces. In VLDB, pages 426--435, 1997."},{"key":"e_1_2_1_17_1","volume-title":"Introduction to algorithms","author":"Cormen T. H.","year":"2009","unstructured":"T. H. Cormen , C. E. Leiserson , R. L. Rivest , and C. Stein . Introduction to algorithms . MIT press , 2009 . T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to algorithms. MIT press, 2009."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1877766.1877767"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.14778\/1938545.1938550"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.14778\/3192965.3192970"},{"key":"e_1_2_1_21_1","volume-title":"Computing discrete Fr\u00e9chet distance. Technical report","author":"Eiter T.","year":"1994","unstructured":"T. Eiter and H. Mannila . Computing discrete Fr\u00e9chet distance. Technical report , 1994 . T. Eiter and H. Mannila. Computing discrete Fr\u00e9chet distance. Technical report, 1994."},{"key":"e_1_2_1_22_1","first-page":"147","volume-title":"ICML","author":"Elkan C.","year":"2003","unstructured":"C. Elkan . Using the triangle inequality to accelerate k-means . In ICML , pages 147 -- 153 , 2003 . C. Elkan. Using the triangle inequality to accelerate k-means. In ICML, pages 147--153, 2003."},{"key":"e_1_2_1_23_1","first-page":"226","volume-title":"SIGKDD","author":"Ester M.","year":"1996","unstructured":"M. Ester , H.-P. Kriegel , J. Sander , and X. Xu . A density-based algorithm for discovering clusters in large spatial databases with noise . In SIGKDD , pages 226 -- 231 , 1996 . M. Ester, H.-P. Kriegel, J. Sander, and X. Xu. A density-based algorithm for discovering clusters in large spatial databases with noise. In SIGKDD, pages 226--231, 1996."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.12107"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/846218.847263"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060650"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2424321.2424355"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972801.12"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/TMC.2013.119"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-011-0262-6"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/tpami.2002.1017616"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.5555\/1287369.1287405"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-0266(199606)17:6<441::AID-SMJ819>3.0.CO;2-G"},{"key":"e_1_2_1_34_1","doi-asserted-by":"crossref","first-page":"593","DOI":"10.1145\/1247480.1247546","volume-title":"SIGMOD","author":"Lee J.-g.","year":"2007","unstructured":"J.-g. Lee , J. Han , and K.-Y. Whang . Trajectory clustering : A partition-and-group framework . In SIGMOD , pages 593 -- 604 , 2007 . J.-g. Lee, J. Han, and K.-Y. Whang. Trajectory clustering: A partition-and-group framework. In SIGMOD, pages 593--604, 2007."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-12098-5_3"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1982.1056489"},{"key":"e_1_2_1_37_1","first-page":"352","volume-title":"GIS","author":"Lou Y.","year":"2009","unstructured":"Y. Lou , C. Zhang , Y. Zheng , X. Xie , W. Wang , and Y. Huang . Map-matching for low-sampling-rate GPS trajectories . In GIS , pages 352 -- 361 , 2009 . Y. Lou, C. Zhang, Y. Zheng, X. Xie, W. Wang, and Y. Huang. Map-matching for low-sampling-rate GPS trajectories. In GIS, pages 352--361, 2009."},{"issue":"233","key":"e_1_2_1_38_1","first-page":"281","article-title":"Some methods for classification and analysis of multivariate observations","volume":"1","author":"Macqueen J.","year":"1967","unstructured":"J. Macqueen . Some methods for classification and analysis of multivariate observations . Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability , 1 ( 233 ): 281 -- 297 , 1967 . J. Macqueen. Some methods for classification and analysis of multivariate observations. Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability, 1(233):281--297, 1967.","journal-title":"Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.5555\/3118756.3119008"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.14778\/2002974.2002978"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.eswa.2008.01.039"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2009.57"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1177\/0361198106198500103"},{"key":"e_1_2_1_44_1","first-page":"3","article-title":"A survey of Venn diagrams","volume":"4","author":"Ruskey F.","year":"1997","unstructured":"F. Ruskey and M. Weston . A survey of Venn diagrams . Electronic Journal of Combinatorics , 4 : 3 , 1997 . F. Ruskey and M. Weston. A survey of Venn diagrams. Electronic Journal of Combinatorics, 4:3, 1997.","journal-title":"Electronic Journal of Combinatorics"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.5555\/876875.878994"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2017.2776268"},{"key":"e_1_2_1_47_1","unstructured":"S. Wang Z. Bao J. S. Culpepper T. Sellis and X. Qin. Fast large-scale trajectory clustering. https:\/\/t4research.github.io\/k-paths-tr.pdf. S. Wang Z. Bao J. S. Culpepper T. Sellis and X. Qin. Fast large-scale trajectory clustering. https:\/\/t4research.github.io\/k-paths-tr.pdf."},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/3209978.3209989"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/3289600.3290615"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2014.2347286"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1109\/IJCNN.2017.7966345"},{"key":"e_1_2_1_52_1","first-page":"201","volume-title":"ICDE","author":"Yi B.-k.","year":"1997","unstructured":"B.-k. Yi and F. Park . Effcient retrieval of similar time sequences under time warping . In ICDE , pages 201 -- 208 , 1997 . B.-k. Yi and F. Park. Effcient retrieval of similar time sequences under time warping. In ICDE, pages 201--208, 1997."},{"key":"e_1_2_1_53_1","first-page":"311","volume-title":"SODA","author":"Yianilos P. N.","year":"1993","unstructured":"P. N. Yianilos . Data structures and algorithms for nearest neighbor search in general metric spaces . In SODA , pages 311 -- 321 , 1993 . P. N. Yianilos. Data structures and algorithms for nearest neighbor search in general metric spaces. In SODA, pages 311--321, 1993."},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10462-016-9477-7"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2019.00115"},{"key":"e_1_2_1_56_1","first-page":"99","volume-title":"GIS","author":"Yuan J.","year":"2010","unstructured":"J. Yuan , Y. Zheng , C. Zhang , W. Xie , X. Xie , G. Sun , and Y. Huang . T-drive: Driving directions based on taxi trajectories . In GIS , pages 99 -- 108 , 2010 . J. Yuan, Y. Zheng, C. Zhang, W. Xie, X. Xie, G. Sun, and Y. Huang. T-drive: Driving directions based on taxi trajectories. In GIS, pages 99--108, 2010."},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/3219819.3219946"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/3292500.3330829"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132956.1132959"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3357377.3357380","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,23]],"date-time":"2023-09-23T03:59:50Z","timestamp":1695441590000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3357377.3357380"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,9]]},"references-count":59,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2019,9,15]]}},"alternative-id":["10.14778\/3357377.3357380"],"URL":"https:\/\/doi.org\/10.14778\/3357377.3357380","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2019,9]]}}}