{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,2]],"date-time":"2026-10-02T18:17:00Z","timestamp":1790965020094,"version":"4.1.0"},"reference-count":66,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2023,11,13]],"date-time":"2023-11-13T00:00:00Z","timestamp":1699833600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100012226","name":"Fundamental Research Funds for the Central Universities","doi-asserted-by":"crossref","award":["2021YJS030"],"award-info":[{"award-number":["2021YJS030"]}],"id":[{"id":"10.13039\/501100012226","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2023,11,13]]},"abstract":"<jats:p>Given an origin (O), a destination (D), and a departure time (T), an Origin-Destination (OD) travel time oracle~(ODT-Oracle) returns an estimate of the time it takes to travel from O to D when departing at T. ODT-Oracles serve important purposes in map-based services. To enable the construction of such oracles, we provide a travel-time estimation (TTE) solution that leverages historical trajectories to estimate time-varying travel times for OD pairs.<\/jats:p>\n                  <jats:p>The problem is complicated by the fact that multiple historical trajectories with different travel times may connect an OD pair, while trajectories may vary from one another. To solve the problem, it is crucial to remove outlier trajectories when doing travel time estimation for future queries.<\/jats:p>\n                  <jats:p>We propose a novel, two-stage framework called Diffusion-based Origin-destination Travel Time Estimation (DOT), that solves the problem. First, DOT employs a conditioned Pixelated Trajectories (PiT) denoiser that enables building a diffusion-based PiT inference process by learning correlations between OD pairs and historical trajectories. Specifically, given an OD pair and a departure time, we aim to infer a PiT. Next, DOT encompasses a Masked Vision Transformer~(MViT) that effectively and efficiently estimates a travel time based on the inferred PiT. We report on extensive experiments on two real-world datasets that offer evidence that DOT is capable of outperforming baseline methods in terms of accuracy, scalability, and explainability.<\/jats:p>","DOI":"10.1145\/3617337","type":"journal-article","created":{"date-parts":[[2023,11,13]],"date-time":"2023-11-13T17:28:39Z","timestamp":1699896519000},"page":"1-27","source":"Crossref","is-referenced-by-count":28,"title":["Origin-Destination Travel Time Oracle for Map-based Services"],"prefix":"10.1145","volume":"1","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2320-9777","authenticated-orcid":false,"given":"Yan","family":"Lin","sequence":"first","affiliation":[{"name":"Beijing Jiaotong University, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0501-9363","authenticated-orcid":false,"given":"Huaiyu","family":"Wan","sequence":"additional","affiliation":[{"name":"Beijing Jiaotong University, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7739-7769","authenticated-orcid":false,"given":"Jilin","family":"Hu","sequence":"additional","affiliation":[{"name":"East China Normal University, Shanghai, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3008-4511","authenticated-orcid":false,"given":"Shengnan","family":"Guo","sequence":"additional","affiliation":[{"name":"Beijing Jiaotong University, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1658-1079","authenticated-orcid":false,"given":"Bin","family":"Yang","sequence":"additional","affiliation":[{"name":"East China Normal University, Shanghai, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5143-3645","authenticated-orcid":false,"given":"Youfang","family":"Lin","sequence":"additional","affiliation":[{"name":"Beijing Jiaotong University, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9697-7670","authenticated-orcid":false,"given":"Christian S.","family":"Jensen","sequence":"additional","affiliation":[{"name":"Aalborg University, Aalborg, Denmark"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2023,11,13]]},"reference":[{"key":"e_1_2_2_1_1","first-page":"17981","article-title":"Structured denoising diffusion models in discrete state-spaces","volume":"34","author":"Austin Jacob","year":"2021","unstructured":"Jacob Austin, Daniel D Johnson, Jonathan Ho, Daniel Tarlow, and Rianne van den Berg. 2021. Structured denoising diffusion models in discrete state-spaces. In NeurIPS, Vol. 34. 17981--17993.","journal-title":"NeurIPS"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.omega.2012.09.004"},{"key":"e_1_2_2_3_1","volume-title":"A survey on map-matching algorithms","author":"Chao Pingfu","unstructured":"Pingfu Chao, Yehong Xu, Wen Hua, and Xiaofang Zhou. 2020. A survey on map-matching algorithms. In ADC. Springer, 121--133."},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2939672.2939785"},{"key":"e_1_2_2_5_1","volume-title":"Dzmitry Bahdanau, Fethi Bougares, Holger Schwenk, and Yoshua Bengio.","author":"Cho Kyunghyun","year":"2014","unstructured":"Kyunghyun Cho, Bart van Merrienboer, cC aglar G\u00fc lcc ehre, Dzmitry Bahdanau, Fethi Bougares, Holger Schwenk, and Yoshua Bengio. 2014. Learning Phrase Representations using RNN Encoder-Decoder for Statistical Machine Translation. In EMNLP. 1724--1734."},{"key":"e_1_2_2_6_1","doi-asserted-by":"crossref","unstructured":"Theodoros Chondrogiannis Johann Bornholdt Panagiotis Bouros and Michael Grossniklaus. 2022. History oblivious route recovery on road networks. In SIGSPATIAL. 1--10.","DOI":"10.1145\/3557915.3560979"},{"key":"e_1_2_2_7_1","volume-title":"Planning models for freight transportation. European journal of operational research","author":"Crainic Teodor Gabriel","year":"1997","unstructured":"Teodor Gabriel Crainic and Gilbert Laporte. 1997. Planning models for freight transportation. European journal of operational research, Vol. 97, 3 (1997), 409--438."},{"key":"e_1_2_2_8_1","unstructured":"Alexey Dosovitskiy Lucas Beyer Alexander Kolesnikov Dirk Weissenborn Xiaohua Zhai Thomas Unterthiner Mostafa Dehghani Matthias Minderer Georg Heigold Sylvain Gelly Jakob Uszkoreit and Neil Houlsby. 2021. An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale. In ICLR."},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3178876.3186058"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3394486.3403386"},{"key":"e_1_2_2_11_1","doi-asserted-by":"crossref","unstructured":"Yunchong Gan Haoyu Zhang and Mingjie Wang. 2021. Travel Time Estimation Based on Neural Network with Auxiliary Loss. In SIGSPATIAL. 642--645.","DOI":"10.1145\/3474717.3488238"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-020-00608-7"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v34i01.5337"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.14778\/3523210.3523225"},{"key":"e_1_2_2_15_1","volume-title":"Gaussian error linear units (gelus). arXiv preprint arXiv:1606.08415","author":"Hendrycks Dan","year":"2016","unstructured":"Dan Hendrycks and Kevin Gimpel. 2016. Gaussian error linear units (gelus). arXiv preprint arXiv:1606.08415 (2016)."},{"key":"e_1_2_2_16_1","first-page":"6840","article-title":"Denoising diffusion probabilistic models","volume":"33","author":"Ho Jonathan","year":"2020","unstructured":"Jonathan Ho, Ajay Jain, and Pieter Abbeel. 2020. Denoising diffusion probabilistic models. In NeurIPS, Vol. 33. 6840--6851.","journal-title":"NeurIPS"},{"key":"e_1_2_2_17_1","volume-title":"Long short-term memory. Neural computation","author":"Hochreiter Sepp","year":"1997","unstructured":"Sepp Hochreiter and J\u00fcrgen Schmidhuber. 1997. Long short-term memory. Neural computation, Vol. 9, 8 (1997), 1735--1780."},{"key":"e_1_2_2_18_1","doi-asserted-by":"crossref","unstructured":"Shuai Huang Yong Wang Tianyu Zhao and Guoliang Li. 2021. A learning-based method for computing shortest path distances on road networks. In ICDE. 360--371.","DOI":"10.1109\/ICDE51399.2021.00038"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v25i1.7855"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.56.5018"},{"key":"e_1_2_2_21_1","volume-title":"Jensen and Nerius Tradivs auskas","author":"Christian","year":"2009","unstructured":"Christian S. Jensen and Nerius Tradivs auskas. 2009. Map Matching. In Encyclopedia of Database Systems. 1692--1696."},{"key":"e_1_2_2_22_1","unstructured":"Guangyin Jin Huan Yan Fuxian Li Yong Li and Jincai Huang. 2021. Hierarchical neural architecture search for travel time estimation. In SIGSPATIAL. 91--94."},{"key":"e_1_2_2_23_1","unstructured":"Ishan Jindal Xuewen Chen Matthew Nokleby Jieping Ye et al. 2017. A unified neural network approach for estimating travel time and distance for a taxi trip. arXiv preprint arXiv:1710.04350 (2017)."},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/321765.321768"},{"key":"e_1_2_2_25_1","first-page":"3146","article-title":"Lightgbm: A highly efficient gradient boosting decision tree","volume":"30","author":"Ke Guolin","year":"2017","unstructured":"Guolin Ke, Qi Meng, Thomas Finley, Taifeng Wang, Wei Chen, Weidong Ma, Qiwei Ye, and Tie-Yan Liu. 2017. Lightgbm: A highly efficient gradient boosting decision tree. In NeurIPS, Vol. 30. 3146--3154.","journal-title":"NeurIPS"},{"key":"e_1_2_2_26_1","volume-title":"Diffwave: A versatile diffusion model for audio synthesis. arXiv preprint arXiv:2009.09761","author":"Kong Zhifeng","year":"2020","unstructured":"Zhifeng Kong, Wei Ping, Jiaji Huang, Kexin Zhao, and Bryan Catanzaro. 2020. Diffwave: A versatile diffusion model for audio synthesis. arXiv preprint arXiv:2009.09761 (2020)."},{"key":"e_1_2_2_27_1","doi-asserted-by":"crossref","unstructured":"Xiucheng Li Gao Cong and Yun Cheng. 2020. Spatial transition learning on road networks with deep probabilistic models. In ICDE. 349--360.","DOI":"10.1109\/ICDE48307.2020.00037"},{"key":"e_1_2_2_28_1","doi-asserted-by":"crossref","unstructured":"Xiucheng Li Gao Cong Aixin Sun and Yun Cheng. 2019. Learning travel time distributions with deep generative model. In WWW. 1017--1027.","DOI":"10.1145\/3308558.3313418"},{"key":"e_1_2_2_29_1","doi-asserted-by":"crossref","unstructured":"Yaguang Li Dingxiong Deng Ugur Demiryurek Cyrus Shahabi and Siva Ravada. 2015. Towards fast and accurate solutions to vehicle routing in a large-scale and dynamic environment. In SSTD. 119--136.","DOI":"10.1007\/978-3-319-22363-6_7"},{"key":"e_1_2_2_30_1","doi-asserted-by":"crossref","unstructured":"Yaguang Li Kun Fu Zheng Wang Cyrus Shahabi Jieping Ye and Yan Liu. 2018. Multi-task representation learning for travel time estimation. In ACM SIGKDD. 1695--1704.","DOI":"10.1145\/3219819.3220033"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v35i5.16548"},{"key":"e_1_2_2_32_1","first-page":"1","article-title":"Transportation cost and benefit analysis","volume":"31","author":"Litman Todd","year":"2009","unstructured":"Todd Litman. 2009. Transportation cost and benefit analysis. Victoria Transport Policy Institute, Vol. 31 (2009), 1--19.","journal-title":"Victoria Transport Policy Institute"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2017.2773492"},{"key":"e_1_2_2_34_1","doi-asserted-by":"crossref","unstructured":"Huiping Liu Cheqing Jin Bin Yang and Aoying Zhou. 2018. Finding Top-k Optimal Sequenced Routes. In ICDE. 569--580.","DOI":"10.1109\/ICDE.2018.00058"},{"key":"e_1_2_2_35_1","volume-title":"A convnet for the","author":"Liu Zhuang","year":"2020","unstructured":"Zhuang Liu, Hanzi Mao, Chao-Yuan Wu, Christoph Feichtenhofer, Trevor Darrell, and Saining Xie. 2022. A convnet for the 2020s. In IEEE CVPR. 11976--11986."},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1553-2712.1998.tb02493.x"},{"key":"e_1_2_2_37_1","unstructured":"Adam Paszke Sam Gross Francisco Massa Adam Lerer James Bradbury Gregory Chanan Trevor Killeen Zeming Lin Natalia Gimelshein Luca Antiga et al. 2019. PyTorch: An imperative style high-performance deep learning library. In NeurIPS. 8024--8035."},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.14778\/3397230.3397248"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-019-00585-6"},{"key":"e_1_2_2_40_1","volume-title":"High-resolution image synthesis with latent diffusion models","author":"Rombach Robin","unstructured":"Robin Rombach, Andreas Blattmann, Dominik Lorenz, Patrick Esser, and Bj\u00f6rn Ommer. 2022. High-resolution image synthesis with latent diffusion models. In IEEE CVPR. 10684--10695."},{"key":"e_1_2_2_41_1","volume-title":"U-net: Convolutional networks for biomedical image segmentation. In MICCAI. 234--241.","author":"Ronneberger Olaf","year":"2015","unstructured":"Olaf Ronneberger, Philipp Fischer, and Thomas Brox. 2015. U-net: Convolutional networks for biomedical image segmentation. In MICCAI. 234--241."},{"key":"e_1_2_2_42_1","doi-asserted-by":"crossref","unstructured":"Sijie Ruan Zi Xiong Cheng Long Yiheng Chen Jie Bao Tianfu He Ruiyuan Li Shengnan Wu Zhongyuan Jiang and Yu Zheng. 2020. Doing in One Go: Delivery Time Inference Based on Couriers' Trajectories. In ACM SIGKDD. 2813--2821.","DOI":"10.1145\/3394486.3403332"},{"key":"e_1_2_2_43_1","doi-asserted-by":"crossref","unstructured":"Jagan Sankaranarayanan and Hanan Samet. 2009. Distance Oracles for Spatial Networks. In ICDE. 652--663.","DOI":"10.1109\/ICDE.2009.53"},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687763"},{"key":"e_1_2_2_45_1","unstructured":"Jascha Sohl-Dickstein Eric Weiss Niru Maheswaranathan and Surya Ganguli. 2015. Deep unsupervised learning using nonequilibrium thermodynamics. In ICML. 2256--2265."},{"key":"e_1_2_2_46_1","first-page":"11895","article-title":"Generative modeling by estimating gradients of the data distribution","volume":"32","author":"Song Yang","year":"2019","unstructured":"Yang Song and Stefano Ermon. 2019. Generative modeling by estimating gradients of the data distribution. In NeurIPS, Vol. 32. 11895--11907.","journal-title":"NeurIPS"},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/MIS.2022.3173427"},{"key":"e_1_2_2_48_1","first-page":"24804","article-title":"CSDI: Conditional score-based diffusion models for probabilistic time series imputation","volume":"34","author":"Tashiro Yusuke","year":"2021","unstructured":"Yusuke Tashiro, Jiaming Song, Yang Song, and Stefano Ermon. 2021. CSDI: Conditional score-based diffusion models for probabilistic time series imputation. In NeurIPS, Vol. 34. 24804--24816.","journal-title":"NeurIPS"},{"key":"e_1_2_2_49_1","first-page":"5998","article-title":"Attention is all you need","volume":"30","author":"Vaswani Ashish","year":"2017","unstructured":"Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, \u0141ukasz Kaiser, and Illia Polosukhin. 2017. Attention is all you need. In NeurIPS, Vol. 30. 5998--6008.","journal-title":"NeurIPS"},{"key":"e_1_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.1109\/TITS.2022.3145382"},{"key":"e_1_2_2_51_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v32i1.11877"},{"key":"e_1_2_2_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/3324926"},{"key":"e_1_2_2_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/3446344"},{"key":"e_1_2_2_54_1","doi-asserted-by":"crossref","unstructured":"Yilun Wang Yu Zheng and Yexiang Xue. 2014. Travel time estimation of a path using sparse trajectories. In ACM SIGKDD. 25--34.","DOI":"10.1145\/2623330.2623656"},{"key":"e_1_2_2_55_1","doi-asserted-by":"crossref","unstructured":"Zheng Wang Kun Fu and Jieping Ye. 2018a. Learning to estimate the travel time. In ACM SIGKDD. 858--866.","DOI":"10.1145\/3219819.3219900"},{"key":"e_1_2_2_56_1","volume-title":"Package pick-up route prediction via modeling couriers' spatial-temporal behaviors","author":"Wen Haomin","unstructured":"Haomin Wen, Youfang Lin, Fan Wu, Huaiyu Wan, Shengnan Guo, Lixia Wu, Chao Song, and Yinghui Xu. 2021. Package pick-up route prediction via modeling couriers' spatial-temporal behaviors. In IEEE ICDE. 2141--2146."},{"key":"e_1_2_2_57_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v33i01.3301774"},{"key":"e_1_2_2_58_1","doi-asserted-by":"crossref","unstructured":"Hao Wu Jiangyun Mao Weiwei Sun Baihua Zheng Hanyuan Zhang Ziyang Chen and Wei Wang. 2016. Probabilistic robust route recovery with spatio-temporal dynamics. In SIGKDD. 1915--1924.","DOI":"10.1145\/2939672.2939843"},{"key":"e_1_2_2_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/3466686"},{"key":"e_1_2_2_60_1","volume-title":"Tadnm: A transportation-mode aware deep neural model for travel time estimation. In DASFAA. 468--484.","author":"Xu Saijun","year":"2020","unstructured":"Saijun Xu, Jiajie Xu, Rui Zhou, Chengfei Liu, Zhixu Li, and An Liu. 2020. Tadnm: A transportation-mode aware deep neural model for travel time estimation. In DASFAA. 468--484."},{"key":"e_1_2_2_61_1","doi-asserted-by":"publisher","DOI":"10.1155\/2022\/6622734"},{"key":"e_1_2_2_62_1","first-page":"3153","article-title":"Context-Aware Path Ranking in Road Networks","volume":"34","author":"Yang Sean Bin","year":"2022","unstructured":"Sean Bin Yang, Chenjuan Guo, and Bin Yang. 2022a. Context-Aware Path Ranking in Road Networks. IEEE Trans. Knowl. Data Eng., Vol. 34, 7 (2022), 3153--3168.","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"e_1_2_2_63_1","doi-asserted-by":"crossref","unstructured":"Haitao Yuan Guoliang Li Zhifeng Bao and Ling Feng. 2020. Effective travel time estimation: When historical trajectories over road networks matter. In SIGMOD. 2135--2149.","DOI":"10.1145\/3318464.3389771"},{"key":"e_1_2_2_64_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2019.2891537"},{"key":"e_1_2_2_65_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v35i12.17325"},{"key":"e_1_2_2_66_1","volume-title":"3d shape generation and completion through point-voxel diffusion","author":"Zhou Linqi","unstructured":"Linqi Zhou, Yilun Du, and Jiajun Wu. 2021a. 3d shape generation and completion through point-voxel diffusion. In IEEE ICCV. 5826--5835."}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3617337","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3617337","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T12:45:53Z","timestamp":1750164353000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3617337"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,11,13]]},"references-count":66,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2023,11,13]]}},"alternative-id":["10.1145\/3617337"],"URL":"https:\/\/doi.org\/10.1145\/3617337","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,11,13]]}}}