{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,12]],"date-time":"2025-11-12T20:43:26Z","timestamp":1762980206423,"version":"3.41.0"},"reference-count":29,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2015,10,23]],"date-time":"2015-10-23T00:00:00Z","timestamp":1445558400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["61070005, 61472453 and U1401256"],"award-info":[{"award-number":["61070005, 61472453 and U1401256"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Science and Technology Planning Project of Guangdong Province, China","award":["2014A080802003"],"award-info":[{"award-number":["2014A080802003"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2015,10,23]]},"abstract":"<jats:p>\n            In this article, we study an optimal location query based on a road network. Specifically, given a road network containing clients and servers, an optimal location query finds a location on the road network such that when a new server is set up at this location, a certain cost function computed based on the clients and servers (including the new server) is optimized. Two types of cost functions, namely, MinMax and MaxSum, have been used for this query. The optimal location query problem with MinMax as the cost function is called the MinMax query, which finds a location for setting up a new server such that the maximum cost of a client being served by his\/her closest server is minimized. The optimal location query problem with MaxSum as the cost function is called the MaxSum query, which finds a location for setting up a new server such that the sum of the weights of clients attracted by the new server is maximized. The MinMax query and the MaxSum query correspond to two types of optimal location query with the objectives defined from the clients' perspective and from the new server's perspective, respectively. Unfortunately, the existing solutions for the optimal query problem are not efficient. In this article, we propose an efficient algorithm, namely,\n            <jats:italic>MinMax-Alg<\/jats:italic>\n            (\n            <jats:italic>MaxSum-Alg<\/jats:italic>\n            ), for the MinMax (MaxSum) query, which is based on a novel idea of\n            <jats:italic>nearest location component<\/jats:italic>\n            . We also discuss two extensions of the optimal location query, namely, the optimal multiple-location query and the optimal location query on a 3D road network. Extensive experiments were conducted, showing that our algorithms are faster than the state of the art by at least an order of magnitude on large real benchmark datasets. For example, in our largest real datasets, the state of the art ran for more than 10 (12) hours while our algorithm ran within 3 (2) minutes only for the MinMax (MaxSum) query, that is, our algorithm ran at least 200 (600) times faster than the state of the art.\n          <\/jats:p>","DOI":"10.1145\/2818179","type":"journal-article","created":{"date-parts":[[2015,10,24]],"date-time":"2015-10-24T18:27:12Z","timestamp":1445711232000},"page":"1-41","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":18,"title":["Optimal Location Queries in Road Networks"],"prefix":"10.1145","volume":"40","author":[{"given":"Zitong","family":"Chen","sequence":"first","affiliation":[{"name":"Sun Yat-sen University, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yubao","family":"Liu","sequence":"additional","affiliation":[{"name":"Sun Yat-sen University, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Raymond Chi-Wing","family":"Wong","sequence":"additional","affiliation":[{"name":"The Hong Kong University of Science and Technology, Hong Kong"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jiamin","family":"Xiong","sequence":"additional","affiliation":[{"name":"Sun Yat-sen University, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ganglin","family":"Mai","sequence":"additional","affiliation":[{"name":"Sun Yat-sen University, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Cheng","family":"Long","sequence":"additional","affiliation":[{"name":"The Hong Kong University of Science and Technology"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2015,10,23]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1463434.1463524"},{"key":"e_1_2_2_2_1","volume-title":"Proceedings of the Canadian Conference on Computational Geometry (CCCG'05)","author":"Cabello Sergio","year":"2005","unstructured":"Sergio Cabello , Jose Miguel Diaz-Banez , Stefan Langerman , Carlos Seara , and Inmaculada Ventura . 2005 . Reverse facility location problems . In Proceedings of the Canadian Conference on Computational Geometry (CCCG'05) . 68--71. Sergio Cabello, Jose Miguel Diaz-Banez, Stefan Langerman, Carlos Seara, and Inmaculada Ventura. 2005. Reverse facility location problems. In Proceedings of the Canadian Conference on Computational Geometry (CCCG'05). 68--71."},{"key":"e_1_2_2_3_1","volume-title":"Proceedings of the European Workshop on Computational Geometry (EWCG'06)","author":"Cardinal Jean","year":"2006","unstructured":"Jean Cardinal and Stefan Langerman . 2006 . Min-max-min geometric facility location problems . In Proceedings of the European Workshop on Computational Geometry (EWCG'06) . 149--152. Jean Cardinal and Stefan Langerman. 2006. Min-max-min geometric facility location problems. In Proceedings of the European Workshop on Computational Geometry (EWCG'06). 149--152."},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ins.2015.02.009"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2612172"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.14778\/2350229.2350230"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-04245-8"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01386390"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/11535331_10"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1002\/1097-0037(200010)36:3<156::AID-NET2>3.0.CO;2-L"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2063576.2063972"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31235-9_35"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1869790.1869866"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2424321.2424330"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10707-013-0179-x"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(89)90136-1"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/MDM.2013.24"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/0377-2217(83)90181-9"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-012-0527-4"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/874063.875567"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2012.45"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.29.4.498"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687754"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-011-0230-1"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2011.5767845"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2063576.2063788"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-013-0347-5"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.5555\/1182635.1164183"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2011.5767892"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2818179","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2818179","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:39:01Z","timestamp":1750221541000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2818179"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,10,23]]},"references-count":29,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2015,10,23]]}},"alternative-id":["10.1145\/2818179"],"URL":"https:\/\/doi.org\/10.1145\/2818179","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"type":"print","value":"0362-5915"},{"type":"electronic","value":"1557-4644"}],"subject":[],"published":{"date-parts":[[2015,10,23]]},"assertion":[{"value":"2014-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-05-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-10-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}