{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,11]],"date-time":"2026-03-11T16:33:55Z","timestamp":1773246835660,"version":"3.50.1"},"reference-count":42,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2021,11,29]],"date-time":"2021-11-29T00:00:00Z","timestamp":1638144000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"ARC","award":["DP200102611 and DP190101113"],"award-info":[{"award-number":["DP200102611 and DP190101113"]}]},{"name":"Singtel Cognitive and Artificial Intelligence Lab for Enterprises"},{"name":"Singapore Government through the Industry Alignment Fund - Industry Collaboration Projects Grant, and a Tier-1 project","award":["RG114\/19"],"award-info":[{"award-number":["RG114\/19"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Intell. Syst. Technol."],"published-print":{"date-parts":[[2022,2,28]]},"abstract":"<jats:p>\n            <jats:italic>Traffic bottlenecks<\/jats:italic>\n            are a set of road segments that have an unacceptable level of traffic caused by a poor balance between road capacity and traffic volume. A huge volume of trajectory data which captures realtime traffic conditions in road networks provides promising new opportunities to identify the traffic bottlenecks. In this paper, we define this problem as\n            <jats:italic>trajectory-driven traffic bottleneck identification<\/jats:italic>\n            : Given a road network\n            <jats:italic>R<\/jats:italic>\n            , a trajectory database\n            <jats:italic>T<\/jats:italic>\n            , find a representative set of seed edges of size\n            <jats:italic>K<\/jats:italic>\n            of traffic bottlenecks that influence the highest number of road segments not in the seed set. We show that this problem is NP-hard and propose a framework to find the traffic bottlenecks as follows. First, a traffic spread model is defined which represents changes in traffic volume for each road segment over time. Then, the traffic\n            <jats:italic>diffusion probability<\/jats:italic>\n            between two connected segments and the\n            <jats:italic>residual ratio<\/jats:italic>\n            of traffic volume for each segment can be computed using historical trajectory data. We then propose two different algorithmic approaches to solve the problem. The first one is a best-first algorithm\n            <jats:bold>\n              <jats:monospace>BF<\/jats:monospace>\n            <\/jats:bold>\n            , with an approximation ratio of 1-1\/\n            <jats:italic>e<\/jats:italic>\n            . To further accelerate the identification process in larger datasets, we also propose a sampling-based greedy algorithm\n            <jats:monospace>SG<\/jats:monospace>\n            . Finally, comprehensive experiments using three different datasets compare and contrast various solutions, and provide insights into important efficiency and effectiveness trade-offs among the respective methods.\n          <\/jats:p>","DOI":"10.1145\/3465058","type":"journal-article","created":{"date-parts":[[2021,11,30]],"date-time":"2021-11-30T01:51:27Z","timestamp":1638237087000},"page":"1-21","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Let Trajectories Speak Out the Traffic Bottlenecks"],"prefix":"10.1145","volume":"13","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7299-031X","authenticated-orcid":false,"given":"Hui","family":"Luo","sequence":"first","affiliation":[{"name":"RMIT University, Melbourne VIC, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2477-381X","authenticated-orcid":false,"given":"Zhifeng","family":"Bao","sequence":"additional","affiliation":[{"name":"RMIT University, Melbourne VIC, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gao","family":"Cong","sequence":"additional","affiliation":[{"name":"Nanyang Technological University, Nanyang Ave, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1902-9087","authenticated-orcid":false,"given":"J. Shane","family":"Culpepper","sequence":"additional","affiliation":[{"name":"RMIT University, Melbourne VIC, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nguyen Lu Dang","family":"Khoa","sequence":"additional","affiliation":[{"name":"Data61, CSIRO, Eveleigh NSW, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,11,29]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00607-020-00839-0"},{"key":"e_1_3_2_3_2","volume-title":"The 85th Annual Meeting of Transportation Research Board","author":"Bertini Robert L.","year":"2006","unstructured":"Robert L. Bertini. 2006. You are the traffic jam: An examination of congestion measures. In The 85th Annual Meeting of Transportation Research Board."},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.5555\/2900728.2900813"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.14778\/2904121.2904122"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/2086737.2086741"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.14778\/2047485.2047492"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2016.2621038"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3183738"},{"key":"e_1_3_2_10_2","volume-title":"Traffic Bottlenecks: Identification and Solutions","author":"Hale David","year":"2016","unstructured":"David Hale, Ramanujan Jagannathan, Michalis Xyntarakis, Peng Su, Ximiao Jiang, Jiaqi Ma, Jia Hu, Cory Krause, et\u00a0al. 2016. Traffic Bottlenecks: Identification and Solutions. Technical Report. United States Federal Highway Administration. Office of Operations Research."},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1520-6750(199809)45:6<615::AID-NAV5>3.0.CO;2-5"},{"issue":"5","key":"e_1_3_2_12_2","first-page":"2191","article-title":"Deep architecture for traffic flow prediction: Deep belief networks with multitask learning","volume":"15","author":"Huang Wenhao","year":"2014","unstructured":"Wenhao Huang, Guojie Song, Haikun Hong, and Kunqing Xie. 2014. Deep architecture for traffic flow prediction: Deep belief networks with multitask learning. TITS 15, 5 (2014), 2191\u20132201.","journal-title":"TITS"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.3141\/2422-01"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.5555\/2900423.2900443"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/956750.956769"},{"key":"e_1_3_2_16_2","unstructured":"Phil Lasley. 2019. Urban Mobility Report. (2019)."},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2018.2807843"},{"key":"e_1_3_2_18_2","volume-title":"Proc. ICLR","author":"Li Yaguang","year":"2018","unstructured":"Yaguang Li, Rose Yu, Cyrus Shahabi, and Yan Liu. 2018. Diffusion convolutional recurrent neural network: Data-driven traffic forecasting. In Proc. ICLR."},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11432-008-0038-9"},{"key":"e_1_3_2_20_2","first-page":"647","volume-title":"Proc. DASFAA","author":"Luo Hui","year":"2018","unstructured":"Hui Luo, Farhana M. Choudhury, Zhifeng Bao, J. Shane Culpepper, and Bang Zhang. 2018. MaxBRkNN queries for streaming geo-data. In Proc. DASFAA. 647\u2013664."},{"issue":"2","key":"e_1_3_2_21_2","first-page":"865","article-title":"Traffic flow prediction with big data: A deep learning approach","volume":"16","author":"Lv Yisheng","year":"2014","unstructured":"Yisheng Lv, Yanjie Duan, Wenwen Kang, Zhengxi Li, and Fei-Yue Wang. 2014. Traffic flow prediction with big data: A deep learning approach. TITS 16, 2 (2014), 865\u2013873.","journal-title":"TITS"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1109\/TITS.2009.2026312"},{"issue":"4","key":"e_1_3_2_23_2","article-title":"Measuring urban traffic congestion-a review.","volume":"2","author":"Rao Amudapuram Mohan","year":"2012","unstructured":"Amudapuram Mohan Rao and Kalaga Ramachandra Rao. 2012. Measuring urban traffic congestion-a review.International Journal for Traffic & Transport Engineering 2, 4 (2012).","journal-title":"International Journal for Traffic & Transport Engineering"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.5555\/3104482.3104553"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1038\/s41467-020-15353-2"},{"key":"e_1_3_2_26_2","volume-title":"Traffic Congestion and Reliability: Linking Solutions to Problems","author":"Systematics Cambridge","year":"2004","unstructured":"Cambridge Systematics. 2004. Traffic Congestion and Reliability: Linking Solutions to Problems. Technical Report. United States Federal Highway Administration."},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2593670"},{"key":"e_1_3_2_28_2","article-title":"A survey on modern deep neural network for traffic prediction: Trends, methods and challenges","author":"Tedjopurnomo David Alexander","year":"2020","unstructured":"David Alexander Tedjopurnomo, Zhifeng Bao, Baihua Zheng, Farhana Choudhury, and AK Qin. 2020. A survey on modern deep neural network for traffic prediction: Trends, methods and challenges. TKDE (2020).","journal-title":"TKDE"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1145\/3292500.3330824"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1145\/3440207"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1145\/3209978.3209989"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1145\/1835804.1835935"},{"issue":"2","key":"e_1_3_2_33_2","first-page":"583","article-title":"Discovery of critical nodes in road networks through mining from vehicle trajectories","volume":"20","author":"Xu Ming","year":"2018","unstructured":"Ming Xu, Jianping Wu, Mengqi Liu, Yunpeng Xiao, Haohan Wang, and Dongmei Hu. 2018. Discovery of critical nodes in road networks through mining from vehicle trajectories. TITS 20, 2 (2018), 583\u2013593.","journal-title":"TITS"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1080\/13658816.2017.1400548"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.5555\/3304222.3304273"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1016\/S2095-7564(15)30281-6"},{"key":"e_1_3_2_37_2","first-page":"1","volume-title":"Proc. ICC","author":"Yue Wenwei","year":"2018","unstructured":"Wenwei Yue, Changle Li, and Guoqiang Mao. 2018. Urban traffic bottleneck identification based on congestion propagation. In Proc. ICC. 1\u20136."},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1145\/3219819.3219946"},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.1145\/3292500.3330829"},{"key":"e_1_3_2_40_2","first-page":"1243","volume-title":"Big Data","author":"Zhao Baoxin","year":"2017","unstructured":"Baoxin Zhao, Chengzhong Xu, and Siyuan Liu. 2017. A data-driven congestion diffusion model for characterizing traffic in metrocity scales. In Big Data. 1243\u20131252."},{"key":"e_1_3_2_41_2","doi-asserted-by":"publisher","DOI":"10.1145\/2743025"},{"key":"e_1_3_2_42_2","doi-asserted-by":"publisher","DOI":"10.1145\/2629592"},{"key":"e_1_3_2_43_2","first-page":"828","volume-title":"Proc. ICDE","author":"Zhou Zenan","year":"2011","unstructured":"Zenan Zhou, Wei Wu, Xiaohui Li, Mong Li Lee, and Wynne Hsu. 2011. Maxfirst for maxbrknn. In Proc. ICDE. 828\u2013839."}],"container-title":["ACM Transactions on Intelligent Systems and Technology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3465058","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3465058","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:18:25Z","timestamp":1750191505000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3465058"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,11,29]]},"references-count":42,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,2,28]]}},"alternative-id":["10.1145\/3465058"],"URL":"https:\/\/doi.org\/10.1145\/3465058","relation":{},"ISSN":["2157-6904","2157-6912"],"issn-type":[{"value":"2157-6904","type":"print"},{"value":"2157-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,11,29]]},"assertion":[{"value":"2021-01-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-05-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-11-29","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}