{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:17:26Z","timestamp":1750220246735,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":66,"publisher":"ACM","license":[{"start":{"date-parts":[[2022,6,10]],"date-time":"2022-06-10T00:00:00Z","timestamp":1654819200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Hong Kong ITC ITF grants","award":["ITS\/044\/18FX, ITS\/470\/18FX"],"award-info":[{"award-number":["ITS\/044\/18FX, ITS\/470\/18FX"]}]},{"name":"Microsoft Research Asia Collaborative Research Grant"},{"name":"the Hong Kong RGC Theme-based project TRS","award":["T41-603\/20R"],"award-info":[{"award-number":["T41-603\/20R"]}]},{"name":"HKUST-Webank joint research lab grants"},{"name":"National Key Research and Development Program of China Grant","award":["No. 2018AAA0101100"],"award-info":[{"award-number":["No. 2018AAA0101100"]}]},{"name":"HKUST-NAVER\/LINE AI Lab"},{"name":"HKUST Global Strategic Partnership Fund (2021 SJTU-HKUST)"},{"name":"the Hong Kong RGC CRF Project","award":["C6030-18G, C1031-18G, C5026- 18G"],"award-info":[{"award-number":["C6030-18G, C1031-18G, C5026- 18G"]}]},{"name":"Guangdong Basic and Applied Basic Research Foundation","award":["2019B151530001"],"award-info":[{"award-number":["2019B151530001"]}]},{"name":"the National Science Foundation of China (NSFC) under Grant","award":["Nos. U21A20516, 61822201, U1811463, 62076017"],"award-info":[{"award-number":["Nos. U21A20516, 61822201, U1811463, 62076017"]}]},{"name":"the Hong Kong RGC RIF Project","award":["R6020-19"],"award-info":[{"award-number":["R6020-19"]}]},{"name":"China NSFC","award":["No. 61729201"],"award-info":[{"award-number":["No. 61729201"]}]},{"name":"the State Key Laboratory of Software Development Environment Open Funding","award":["No. SKLSDE-2020ZX-07"],"award-info":[{"award-number":["No. SKLSDE-2020ZX-07"]}]},{"name":"the Hong Kong RGC GRF Project","award":["16202218"],"award-info":[{"award-number":["16202218"]}]},{"name":"the Hong Kong RGC AOE Project","award":["the Hong Kong RGC"],"award-info":[{"award-number":["the Hong Kong RGC"]}]},{"name":"Didi-HKUST joint research lab"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2022,6,10]]},"DOI":"10.1145\/3514221.3517831","type":"proceedings-article","created":{"date-parts":[[2022,6,12]],"date-time":"2022-06-12T02:33:49Z","timestamp":1655001229000},"page":"2135-2148","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Faster and Better Solution to Embed Lp Metrics by Tree Metrics"],"prefix":"10.1145","author":[{"given":"Yuxiang","family":"Zeng","sequence":"first","affiliation":[{"name":"The Hong Kong University of Science and Technology, Hong Kong SAR, China"}]},{"given":"Yongxin","family":"Tong","sequence":"additional","affiliation":[{"name":"Beihang University, Beijing, China"}]},{"given":"Lei","family":"Chen","sequence":"additional","affiliation":[{"name":"The Hong Kong University of Science and Technology, Hong Kong SAR, China"}]}],"member":"320","published-online":{"date-parts":[[2022,6,11]]},"reference":[{"unstructured":"2021. Didi Chuxing. Retrieved Oct 21 2021 from https:\/\/www.didiglobal.com\/","key":"e_1_3_2_1_1_1"},{"unstructured":"2021. Foursquare. Retrieved Oct 21 2021 from https:\/\/foursquare.com\/","key":"e_1_3_2_1_3_1"},{"unstructured":"2021. UCAR Inc. Retrieved Oct 21 2021 from https:\/\/www.10101111.com\/","key":"e_1_3_2_1_4_1"},{"key":"e_1_3_2_1_5_1","volume-title":"Guilherme Dias da Fonseca, and David M. Mount","author":"Abdelkader Ahmed","year":"2019","unstructured":"Ahmed Abdelkader, Sunil Arya, Guilherme Dias da Fonseca, and David M. Mount. 2019. Approximate Nearest Neighbor Searching with Non-Euclidean and Weighted Distances. In SODA. 355--372."},{"doi-asserted-by":"crossref","unstructured":"Ittai Abraham Yair Bartal and Ofer Neiman. 2006. Advances in metric embedding theory. In STOC. 271--286.","key":"e_1_3_2_1_6_1","DOI":"10.1145\/1132516.1132557"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_7_1","DOI":"10.1007\/s10878-012-9581-9"},{"key":"e_1_3_2_1_8_1","article-title":"The priority R-tree: A practically efficient and worst-case optimal R-tree","volume":"4","author":"Arge Lars","year":"2008","unstructured":"Lars Arge, Mark de Berg, Herman J. Haverkort, and Ke Yi. 2008. The priority R-tree: A practically efficient and worst-case optimal R-tree. ACM Trans. Database Syst. 4, 1 (2008), 9:1--9:30.","journal-title":"ACM Trans. Database Syst."},{"key":"e_1_3_2_1_9_1","volume-title":"Mount","author":"Arya Sunil","year":"1993","unstructured":"Sunil Arya and David M. Mount. 1993. Approximate Nearest Neighbor Queries in Fixed Dimensions. In SODA. 271--280."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_10_1","DOI":"10.1145\/293347.293348"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_11_1","DOI":"10.1504\/IJCVR.2011.045267"},{"doi-asserted-by":"crossref","unstructured":"Yossi Azar and Noam Touitou. 2019. General Framework for Metric Optimization Problems with Delay or with Deadlines. In FOCS. 11--22.","key":"e_1_3_2_1_12_1","DOI":"10.1109\/FOCS.2019.00013"},{"unstructured":"Arturs Backurs Piotr Indyk Krzysztof Onak Baruch Schieber Ali Vakilian and Tal Wagner. 2019. Scalable Fair Clustering. In ICML. 405--413.","key":"e_1_3_2_1_13_1"},{"doi-asserted-by":"crossref","unstructured":"Yair Bartal. 1996. Probabilistic Approximations of Metric Spaces and Its Algorithmic Applications. In FOCS. 184--193.","key":"e_1_3_2_1_14_1","DOI":"10.1109\/SFCS.1996.548477"},{"doi-asserted-by":"crossref","unstructured":"Yair Bartal. 1998. On Approximating Arbitrary Metrices by Tree Metrics. In STOC. 161--168.","key":"e_1_3_2_1_15_1","DOI":"10.1145\/276698.276725"},{"doi-asserted-by":"crossref","unstructured":"Norbert Beckmann Hans-Peter Kriegel Ralf Schneider and Bernhard Seeger. 1990. The R*-Tree: An Efficient and Robust Access Method for Points and Rectangles. In SIGMOD. 322--331.","key":"e_1_3_2_1_16_1","DOI":"10.1145\/93605.98741"},{"doi-asserted-by":"crossref","unstructured":"Guy E. Blelloch Anupam Gupta and Kanat Tangwongsan. 2012. Parallel probabilistic tree embeddings k-median and buy-at-bulk network design. In SPAA. 205--213.","key":"e_1_3_2_1_17_1","DOI":"10.1145\/2312005.2312045"},{"doi-asserted-by":"crossref","unstructured":"Zhao Chen Peng Cheng Yuxiang Zeng and Lei Chen. 2019. Minimizing Maximum Delay of Task Assignment in Spatial Crowdsourcing. In ICDE. 1454--1465.","key":"e_1_3_2_1_18_1","DOI":"10.1109\/ICDE.2019.00131"},{"doi-asserted-by":"crossref","unstructured":"Christian Coester and Elias Koutsoupias. 2019. The online -taxi problem. In STOC. 1136--1147.","key":"e_1_3_2_1_19_1","DOI":"10.1145\/3313276.3316370"},{"key":"e_1_3_2_1_20_1","first-page":"1","article-title":"Online Facility Location with Deletions","volume":"21","author":"Cygan Marek","year":"2018","unstructured":"Marek Cygan, Artur Czumaj, Marcin Mucha, and Piotr Sankowski. 2018. Online Facility Location with Deletions. In ESA. 21:1--21:15.","journal-title":"ESA."},{"key":"e_1_3_2_1_21_1","volume-title":"Retrieved","author":"Dawes Beman","year":"2021","unstructured":"Beman Dawes, David Abrahams, and Rene Rivera. 2021. Boost C++ Libraries. Retrieved Oct 21, 2021 from https:\/\/www.boost.org\/"},{"key":"e_1_3_2_1_22_1","volume-title":"Overmars","author":"de Berg Mark","year":"2008","unstructured":"Mark de Berg, Otfried Cheong, Marc J. van Kreveld, and Mark H. Overmars. 2008. Computational geometry: algorithms and applications, 3rd Edition. Springer.","edition":"3"},{"key":"e_1_3_2_1_23_1","volume-title":"Retrieved","author":"Chuxing Didi","year":"2021","unstructured":"Didi Chuxing. 2021. GAIA Initiative. Retrieved Oct 21, 2021 from http:\/\/gaia.didichuxing.com"},{"unstructured":"Yunus Esencayi Marco Gaboardi Shi Li and Di Wang. 2019. Facility Location Problem in Differential Privacy Model Revisited. In NeurIPS. 8489--8498.","key":"e_1_3_2_1_24_1"},{"doi-asserted-by":"crossref","unstructured":"Jittat Fakcharoenphol Satish Rao and Kunal Talwar. 2003. A tight bound on approximating arbitrary metrics by tree metrics. In STOC. 448--455.","key":"e_1_3_2_1_25_1","DOI":"10.1145\/780542.780608"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_26_1","DOI":"10.1016\/j.jcss.2004.04.011"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_27_1","DOI":"10.1007\/BF00288933"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_28_1","DOI":"10.1137\/090779759"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_29_1","DOI":"10.1145\/3231591"},{"key":"e_1_3_2_1_30_1","volume-title":"Jon Louis Bentley, and Robert Endre Tarjan","author":"Gabow Harold N.","year":"1984","unstructured":"Harold N. Gabow, Jon Louis Bentley, and Robert Endre Tarjan. 1984. Scaling and Related Techniques for Geometry Problems. In STOC. 135--143."},{"unstructured":"Junhao Gan and Yufei Tao. 2015. DBSCAN Revisited: Mis-Claim Un-Fixability and Approximation. In SIGMOD. 519--530.","key":"e_1_3_2_1_31_1"},{"unstructured":"Jie Gao Leonidas J. Guibas Nikola Milosavljevic and Dengpan Zhou. 2009. Distributed resource management and matching in sensor networks. In IPSN. 97--108.","key":"e_1_3_2_1_32_1"},{"doi-asserted-by":"crossref","unstructured":"Antonin Guttman. 1984. R-Trees: A Dynamic Index Structure for Spatial Searching. In SIGMOD. 47--57.","key":"e_1_3_2_1_33_1","DOI":"10.1145\/971697.602266"},{"doi-asserted-by":"crossref","unstructured":"Sariel Har-Peled. 2001. A Replacement for Voronoi Diagrams of Near Linear Size. In FOCS. 94--103.","key":"e_1_3_2_1_34_1","DOI":"10.1109\/SFCS.2001.959884"},{"volume-title":"Geometric approximation algorithms. Number 173","author":"Har-Peled Sariel","unstructured":"Sariel Har-Peled. 2011. Geometric approximation algorithms. Number 173. American Mathematical Society.","key":"e_1_3_2_1_35_1"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_36_1","DOI":"10.1137\/0213024"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_37_1","DOI":"10.1007\/s00778-017-0472-7"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_38_1","DOI":"10.14778\/2850469.2850470"},{"doi-asserted-by":"crossref","unstructured":"Piotr Indyk. 2001. Algorithmic Applications of Low-Distortion Geometric Embeddings. In FOCS. 10--33.","key":"e_1_3_2_1_39_1","DOI":"10.1109\/SFCS.2001.959878"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_40_1","DOI":"10.1006\/jagm.1993.1026"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_41_1","DOI":"10.1016\/S0020-0190(01)00161-2"},{"unstructured":"Jian Li Amol Deshpande and Samir Khuller. 2009. Minimizing Communication Cost in Distributed Multi-query Processing. In ICDE. 772--783.","key":"e_1_3_2_1_42_1"},{"key":"e_1_3_2_1_43_1","volume-title":"Poplawski","author":"Meyerson Adam","year":"2006","unstructured":"Adam Meyerson, Akash Nanavati, and Laura J. Poplawski. 2006. Randomized online algorithms for minimum metric bipartite matching. In SODA. 954--959."},{"volume-title":"Probability and Computing: Randomized Algorithms and Probabilistic Analysis","author":"Mitzenmacher Michael","unstructured":"Michael Mitzenmacher and Eli Upfal. 2005. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press.","key":"e_1_3_2_1_44_1"},{"volume-title":"Randomized Algorithms","author":"Motwani Rajeev","unstructured":"Rajeev Motwani and Prabhakar Raghavan. 1995. Randomized Algorithms. Cambridge University Press.","key":"e_1_3_2_1_45_1"},{"doi-asserted-by":"crossref","unstructured":"David M. Mount. 2019. New Directions in Approximate Nearest-Neighbor Searching. In CALDAM. 1--15.","key":"e_1_3_2_1_46_1","DOI":"10.1007\/978-3-030-11509-8_1"},{"key":"e_1_3_2_1_47_1","volume-title":"Lowe","author":"Muja Marius","year":"2009","unstructured":"Marius Muja and David G. Lowe. 2009. Fast approximate nearest neighbors with automatic algorithm configuration. In VISAPP. 331--340."},{"key":"e_1_3_2_1_48_1","volume-title":"Lowe","author":"Muja Marius","year":"2021","unstructured":"Marius Muja and David G. Lowe. 2021. FLANN: Fast Library for Approximate Nearest Neighbors. Retrieved Oct 21, 2021 from https:\/\/github.com\/flann-lib\/flann"},{"doi-asserted-by":"crossref","unstructured":"Ofir Pele and Michael Werman. 2010. The quadratic-chi histogram distance family. In ECCV. 749--762.","key":"e_1_3_2_1_49_1","DOI":"10.1007\/978-3-642-15552-9_54"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_50_1","DOI":"10.14778\/3407790.3407829"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_51_1","DOI":"10.1145\/3397506"},{"volume-title":"Foundations of multidimensional and metric data structures","author":"Samet Hanan","unstructured":"Hanan Samet. 2006. Foundations of multidimensional and metric data structures. Academic Press.","key":"e_1_3_2_1_52_1"},{"volume-title":"Encyclopedia of mathematics","author":"Tanton James S","unstructured":"James S Tanton. 2005. Encyclopedia of mathematics. Infobase Publishing.","key":"e_1_3_2_1_53_1"},{"doi-asserted-by":"crossref","unstructured":"Qian Tao Yongxin Tong Zimu Zhou Yexuan Shi Lei Chen and Ke Xu. 2020. Differentially Private Online Task Assignment in Spatial Crowdsourcing: A Tree- based Approach. In ICDE. 517--528.","key":"e_1_3_2_1_54_1","DOI":"10.1109\/ICDE48307.2020.00051"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_55_1","DOI":"10.14778\/2994509.2994523"},{"key":"e_1_3_2_1_56_1","first-page":"2295","article-title":"Two-Sided Online Micro-Task Assignment in Spatial Crowdsourcing","volume":"33","author":"Tong Yongxin","year":"2021","unstructured":"Yongxin Tong, Yuxiang Zeng, Bolin Ding, Libin Wang, and Lei Chen. 2021. Two-Sided Online Micro-Task Assignment in Spatial Crowdsourcing. IEEE Transactions on Knowledge and Data Engineering 33, 5 (2021), 2295--2309.","journal-title":"IEEE Transactions on Knowledge and Data Engineering"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_57_1","DOI":"10.1007\/s00778-019-00568-7"},{"volume-title":"Handbook of discrete and computational geometry","author":"Toth Csaba D","unstructured":"Csaba D Toth, Joseph O'Rourke, and Jacob E Goodman. 2017. Handbook of discrete and computational geometry. Chapman and Hall\/CRC.","key":"e_1_3_2_1_58_1"},{"key":"e_1_3_2_1_59_1","volume-title":"Retrieved","author":"Weinberger Kilian","year":"2021","unstructured":"Kilian Weinberger. 2021. Lecture 2: K-Nearest Neighbors (Curse of Dimensionality). Retrieved Oct 21, 2021 from https:\/\/www.cs.cornell.edu\/courses\/cs4780\/2018fa\/lectures\/lecturenote02_kNN.html"},{"volume-title":"The design of approximation algorithms","author":"Williamson David P","unstructured":"David P Williamson and David B Shmoys. 2011. The design of approximation algorithms. Cambridge university press.","key":"e_1_3_2_1_60_1"},{"key":"e_1_3_2_1_61_1","volume-title":"Ada Wai-Chee Fu, and Xiaokui Xiao","author":"Chi-Wing Wong Raymond","year":"2007","unstructured":"Raymond Chi-Wing Wong, Yufei Tao, Ada Wai-Chee Fu, and Xiaokui Xiao. 2007. On Efficient Spatial Matching. In VLDB. 579--590."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_62_1","DOI":"10.1109\/TSMC.2014.2327053"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_63_1","DOI":"10.14778\/3368289.3368297"},{"doi-asserted-by":"crossref","unstructured":"Yuxiang Zeng Yongxin Tong and Lei Chen. 2021. HST+: An Efficient Index for Embedding Arbitrary Metric Spaces. In ICDE. 648--659.","key":"e_1_3_2_1_64_1","DOI":"10.1109\/ICDE51399.2021.00062"},{"doi-asserted-by":"crossref","unstructured":"Yuxiang Zeng Yongxin Tong Lei Chen and Zimu Zhou. 2018. Latency-Oriented Task Completion via Spatial Crowdsourcing. In ICDE. 317--328.","key":"e_1_3_2_1_65_1","DOI":"10.1109\/ICDE.2018.00037"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_66_1","DOI":"10.14778\/3424573.3424574"},{"doi-asserted-by":"crossref","unstructured":"Boming Zhao Pan Xu Yexuan Shi Yongxin Tong Zimu Zhou and Yuxiang Zeng. 2019. Preference-Aware Task Assignment in On-Demand Taxi Dispatching: An Online Stable Matching Approach. In AAAI. 2245--2252.","key":"e_1_3_2_1_67_1","DOI":"10.1609\/aaai.v33i01.33012245"}],"event":{"sponsor":["SIGMOD ACM Special Interest Group on Management of Data"],"acronym":"SIGMOD\/PODS '22","name":"SIGMOD\/PODS '22: International Conference on Management of Data","location":"Philadelphia PA USA"},"container-title":["Proceedings of the 2022 International Conference on Management of Data"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3514221.3517831","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3514221.3517831","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:30:35Z","timestamp":1750188635000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3514221.3517831"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,10]]},"references-count":66,"alternative-id":["10.1145\/3514221.3517831","10.1145\/3514221"],"URL":"https:\/\/doi.org\/10.1145\/3514221.3517831","relation":{},"subject":[],"published":{"date-parts":[[2022,6,10]]},"assertion":[{"value":"2022-06-11","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}