{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,6]],"date-time":"2026-01-06T13:46:01Z","timestamp":1767707161272},"reference-count":31,"publisher":"Association for Computing Machinery (ACM)","issue":"11","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2017,8]]},"abstract":"\n The popularity of Online To Offline (O2O) service platforms has spurred the need for online task assignment in real-time spatial data, where streams of spatially distributed tasks and workers are matched in real time such that the total number of assigned pairs is maximized. Existing online task assignment models assume that each worker is either assigned a task immediately or waits for a subsequent task at a fixed location once she\/he appears on the platform. Yet in practice a worker may actively move around rather than passively wait in place if no task is assigned. In this paper, we define a new problem\n <u>F<\/u>lexible <u>T<\/u>wo-sided <u>O<\/u>nline task <u>A<\/u>ssignment<\/jats:italic>\n (FTOA). FTOA aims to guide idle workers based on the prediction of tasks and workers so as to increase the total number of assigned worker-task pairs. To address the FTOA problem, we face two challenges: (i) How to generate guidance for idle workers based on the prediction of the spatiotemporal distribution of tasks and workers? (ii) How to leverage the guidance of workers' movements to optimize the online task assignment? To this end, we propose a novel two-step framework, which integrates\n offline prediction<\/jats:italic>\n and\n online task assignment.<\/jats:italic>\n Specifically, we estimate the distributions of tasks and workers per time slot and per unit area, and design an online task assignment algorithm,\n <u>P<\/u>rediction-oriented <u>O<\/u>nline task <u>A<\/u>ssignment in <u>R<\/u>eal-time spatial data<\/jats:italic>\n (POLAR-OP). It yields a 0.47-competitive ratio, which is nearly twice better than that of the state-of-the-art. POLAR-OP also reduces the time complexity to process each newly-arrived task\/worker to O(1). We validate the effectiveness and efficiency of our methods via extensive experiments on both synthetic datasets and real-world datasets from a large-scale taxi-calling platform.\n <\/jats:p>","DOI":"10.14778\/3137628.3137643","type":"journal-article","created":{"date-parts":[[2017,9,7]],"date-time":"2017-09-07T13:35:53Z","timestamp":1504791353000},"page":"1334-1345","source":"Crossref","is-referenced-by-count":114,"title":["Flexible online task assignment in real-time spatial data"],"prefix":"10.14778","volume":"10","author":[{"given":"Yongxin","family":"Tong","sequence":"first","affiliation":[{"name":"Beihang University, Beijing, China"}]},{"given":"Libin","family":"Wang","sequence":"additional","affiliation":[{"name":"Beihang University, Beijing, China"}]},{"given":"Zimu","family":"Zhou","sequence":"additional","affiliation":[{"name":"ETH Zurich, Zurich, Switzerland"}]},{"given":"Bolin","family":"Ding","sequence":"additional","affiliation":[{"name":"Microsoft Research"}]},{"given":"Lei","family":"Chen","sequence":"additional","affiliation":[{"name":"The Hong Kong University of Science and Technology, Hong Kong SAR, China"}]},{"given":"Jieping","family":"Ye","sequence":"additional","affiliation":[{"name":"Didi Research Institute, Beijing, China"}]},{"given":"Ke","family":"Xu","sequence":"additional","affiliation":[{"name":"Beihang University, Beijing, China"}]}],"member":"320","published-online":{"date-parts":[[2017,8]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Didi chuxing. https:\/\/en.wikipedia.org\/wiki\/Didi_Chuxing. Didi chuxing. https:\/\/en.wikipedia.org\/wiki\/Didi_Chuxing."},{"key":"e_1_2_1_2_1","unstructured":"Gigwalk. http:\/\/www.gigwalk.com. Gigwalk. http:\/\/www.gigwalk.com."},{"key":"e_1_2_1_3_1","unstructured":"Grubhub. https:\/\/www.grubhub.com\/. Grubhub. https:\/\/www.grubhub.com\/."},{"key":"e_1_2_1_4_1","unstructured":"Uber. https:\/\/www.uber.com\/. Uber. https:\/\/www.uber.com\/."},{"key":"e_1_2_1_5_1","volume-title":"Network Flows: Theory, Algorithms, and Applications","author":"Ahuya R.","year":"1993","unstructured":"R. Ahuya , T. Magnanti , and J. Orlin . Network Flows: Theory, Algorithms, and Applications . Prentice Hall , 1993 . R. Ahuya, T. Magnanti, and J. Orlin. Network Flows: Theory, Algorithms, and Applications. Prentice Hall, 1993."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2525314.2525370"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2009.72"},{"key":"e_1_2_1_8_1","unstructured":"J. H. Friedman. Greedy function approximation: a gradient boosting machine. Annals of statistics. J. H. Friedman. Greedy function approximation: a gradient boosting machine. Annals of statistics."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-39937-9_15"},{"key":"e_1_2_1_10_1","volume-title":"SODA","author":"Goel G.","year":"2008","unstructured":"G. Goel and A. Mehta . Online budgeted matching in random input models with applications to adwords . In SODA 2008 . G. Goel and A. Mehta. Online budgeted matching in random input models with applications to adwords. In SODA 2008."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2442810.2442828"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2013.0621"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.1220433110"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/100216.100262"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2424321.2424346"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2525314.2525346"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2820783.2820837"},{"key":"e_1_2_1_18_1","volume-title":"Theoretical Computer Science","author":"Mehta A.","year":"2012","unstructured":"A. Mehta . Online matching and ad allocation . Theoretical Computer Science , 2012 . A. Mehta. Online matching and ad allocation. Theoretical Computer Science, 2012."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/TITS.2013.2262376"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/MDM.2014.15"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2016.2565468"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/977401.978084"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732951.2732966"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2729713"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.14778\/2994509.2994523"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2016.7498228"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376621"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/UIC-ATC-ScalCom.2014.68"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-47672-7_87"},{"key":"e_1_2_1_30_1","volume-title":"VLDB","author":"Wong R. C.-W.","year":"2007","unstructured":"R. C.-W. Wong , Y. Tao , A. W.-C. Fu , and X. Xiao . On efficient spatial matching . In VLDB 2007 . R. C.-W. Wong, Y. Tao, A. W.-C. Fu, and X. Xiao. On efficient spatial matching. In VLDB 2007."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/BigData.2016.7840676"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3137628.3137643","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:00:13Z","timestamp":1672221613000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3137628.3137643"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,8]]},"references-count":31,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2017,8]]}},"alternative-id":["10.14778\/3137628.3137643"],"URL":"https:\/\/doi.org\/10.14778\/3137628.3137643","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2017,8]]}}}