{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,21]],"date-time":"2026-02-21T19:28:10Z","timestamp":1771702090283,"version":"3.50.1"},"reference-count":33,"publisher":"Association for Computing Machinery (ACM)","issue":"12","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2016,8]]},"abstract":"<jats:p>Recently, with the development of mobile Internet and smartphones, the &lt;u&gt;o&lt;\/u&gt;nline &lt;u&gt;m&lt;\/u&gt;inimum &lt;u&gt;b&lt;\/u&gt;ipartite &lt;u&gt;m&lt;\/u&gt;atching in real time spatial data (OMBM) problem becomes popular. Specifically, given a set of service providers with specific locations and a set of users who dynamically appear one by one, the OMBM problem is to find a maximum-cardinality matching with minimum total distance following that once a user appears, s\/he must be immediately matched to an unmatched service provider, which cannot be revoked, before subsequent users arrive. To address this problem, existing studies mainly focus on analyzing the worst-case competitive ratios of the proposed online algorithms, but study on the performance of the algorithms in practice is absent. In this paper, we present a comprehensive experimental comparison of the representative algorithms of the OMBM problem. Particularly, we observe a surprising result that the simple and efficient greedy algorithm, which has been considered as the worst due to its exponential worst-case competitive ratio, is significantly more effective than other algorithms. We investigate the results and further show that the competitive ratio of the worst case of the greedy algorithm is actually just a constant, 3.195, in the average-case analysis. We try to clarify a 25-year misunderstanding towards the greedy algorithm and justify that the greedy algorithm is not bad at all. Finally, we provide a uniform implementation for all the algorithms of the OMBM problem and clarify their strengths and weaknesses, which can guide practitioners to select appropriate algorithms for various scenarios.<\/jats:p>","DOI":"10.14778\/2994509.2994523","type":"journal-article","created":{"date-parts":[[2016,9,6]],"date-time":"2016-09-06T15:27:03Z","timestamp":1473175623000},"page":"1053-1064","source":"Crossref","is-referenced-by-count":159,"title":["Online minimum matching in real-time spatial data"],"prefix":"10.14778","volume":"9","author":[{"given":"Yongxin","family":"Tong","sequence":"first","affiliation":[{"name":"Beihang University, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jieying","family":"She","sequence":"additional","affiliation":[{"name":"The Hong Kong University of Science and Technology, Hong Kong SAR, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bolin","family":"Ding","sequence":"additional","affiliation":[{"name":"Microsoft Research, Redmond, WA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lei","family":"Chen","sequence":"additional","affiliation":[{"name":"The Hong Kong University of Science and Technology, Hong Kong SAR, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tianyu","family":"Wo","sequence":"additional","affiliation":[{"name":"Beihang University, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ke","family":"Xu","sequence":"additional","affiliation":[{"name":"Beihang University, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2016,8]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Gigwalk. http:\/\/www.gigwalk.com.  Gigwalk. http:\/\/www.gigwalk.com ."},{"key":"e_1_2_1_2_1","unstructured":"Grubhub. https:\/\/www.grubhub.com\/.  Grubhub. https:\/\/www.grubhub.com\/ ."},{"key":"e_1_2_1_3_1","unstructured":"Shenzhou private cars. http:\/\/zhuanche.zuche.com\/.  Shenzhou private cars. http:\/\/zhuanche.zuche.com\/ ."},{"key":"e_1_2_1_4_1","unstructured":"Source code and datasets. https:\/\/www.cse.ust.hk\/jshe\/OMBM.zip.  Source code and datasets. https:\/\/www.cse.ust.hk\/jshe\/OMBM.zip ."},{"key":"e_1_2_1_5_1","unstructured":"Uber. https:\/\/www.uber.com\/.  Uber. https:\/\/www.uber.com\/ ."},{"key":"e_1_2_1_6_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_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/MDM.2015.55"},{"key":"e_1_2_1_8_1","volume-title":"ESA","author":"Bansal N.","year":"2007","unstructured":"N. Bansal , N. Buchbinder , A. Gupta , and J. S. Naor . An o (log2k)-competitive algorithm for metric bipartite matching . In ESA 2007 . N. Bansal, N. Buchbinder, A. Gupta, and J. S. Naor. An o (log2k)-competitive algorithm for metric bipartite matching. In ESA 2007."},{"key":"e_1_2_1_9_1","volume-title":"Algorithmica","author":"Bansal N.","year":"2014","unstructured":"N. Bansal , N. Buchbinder , A. Gupta , and J. S. Naor . A randomized o (log2k)-competitive algorithm for metric bipartite matching . Algorithmica , 2014 . N. Bansal, N. Buchbinder, A. Gupta, and J. S. Naor. A randomized o (log2k)-competitive algorithm for metric bipartite matching. Algorithmica, 2014."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/1508120"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.14778\/2733004.2733047"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780608"},{"key":"e_1_2_1_13_1","volume-title":"IPSN","author":"Gao J.","year":"2009","unstructured":"J. Gao , L. Guibas , N. Milosavljevic , and D. Zhou . Distributed resource management and matching in sensor networks . In IPSN 2009 . J. Gao, L. Guibas, N. Milosavljevic, and D. Zhou. Distributed resource management and matching in sensor networks. In IPSN 2009."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31594-7_36"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.1220433110"},{"key":"e_1_2_1_16_1","volume-title":"SODA","author":"Kalyanasundaram B.","year":"1991","unstructured":"B. Kalyanasundaram and K. Pruhs . On-line weighted matching . In SODA 1991 . B. Kalyanasundaram and K. Pruhs. On-line weighted matching. In SODA 1991."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1993.1026"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2424321.2424346"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)90042-6"},{"key":"e_1_2_1_20_1","author":"Lee D.-H.","year":"2004","unstructured":"D.-H. Lee , H. Wang , R. Cheu , and S. Teo . Taxi dispatch system based on current demands and real-time traffic conditions. Transportation Research Record: Journal of the Transportation Research Board , 2004 . D.-H. Lee, H. Wang, R. Cheu, and S. Teo. Taxi dispatch system based on current demands and real-time traffic conditions. Transportation Research Record: Journal of the Transportation Research Board, 2004.","journal-title":"Transportation Research Record: Journal of the Transportation Research Board"},{"key":"e_1_2_1_21_1","volume-title":"Unraveling the origin of exponential law in intra-urban human mobility. Scientific reports","author":"Liang X.","year":"2013","unstructured":"X. Liang , J. Zhao , L. Dong , and K. Xu . Unraveling the origin of exponential law in intra-urban human mobility. Scientific reports , 2013 . X. Liang, J. Zhao, L. Dong, and K. Xu. Unraveling the origin of exponential law in intra-urban human mobility. Scientific reports, 2013."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/1109557.1109662"},{"key":"e_1_2_1_23_1","volume-title":"A collaborative multiagent taxi-dispatch system","author":"Seow K. T.","year":"2010","unstructured":"K. T. Seow , N. H. Dang , and D.-H. Lee . A collaborative multiagent taxi-dispatch system . IEEE Transactions on Automation Science and Engineering , 2010 . K. T. Seow, N. H. Dang, and D.-H. Lee. A collaborative multiagent taxi-dispatch system. IEEE Transactions on Automation Science and Engineering, 2010."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2749446"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2015.7113329"},{"key":"e_1_2_1_26_1","author":"She J.","year":"2016","unstructured":"J. She , Y. Tong , L. Chen , and C. C. Cao . Conflict-aware event-participant arrangement and its variant for online setting. IEEE Transactions on Knowledge and Data Engineering , 2016 . J. She, Y. Tong, L. Chen, and C. C. Cao. Conflict-aware event-participant arrangement and its variant for online setting. IEEE Transactions on Knowledge and Data Engineering, 2016.","journal-title":"IEEE Transactions on Knowledge and Data Engineering"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732951.2732966"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2729713"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2016.7498228"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11280-015-0377-6"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376621"},{"key":"e_1_2_1_32_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_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2007.04.001"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2994509.2994523","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:53:23Z","timestamp":1672224803000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2994509.2994523"}},"subtitle":["experiments and analysis"],"short-title":[],"issued":{"date-parts":[[2016,8]]},"references-count":33,"journal-issue":{"issue":"12","published-print":{"date-parts":[[2016,8]]}},"alternative-id":["10.14778\/2994509.2994523"],"URL":"https:\/\/doi.org\/10.14778\/2994509.2994523","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2016,8]]}}}