Efficient algorithms for optimal location queries in road networks

Zitong Chen, Yubao Liu, Raymond Chi-Wing Wong, Jiamin Xiong, Ganglin Mai, Cheng Long

Research output: Chapter in Book/Report/Conference proceedingConference contribution

43 Citations (Scopus)


In this paper, we study the optimal location query problem based on road networks. Specifically, we have a road network on which some clients and servers are located. Each client finds the server that is closest to her for service and her cost of getting served is equal to the (network) distance between the client and the server serving her multiplied by her weight or importance. The optimal location query problem is to find a location for setting up a new server such that the maximum cost of clients being served by the servers (including the new server) is minimized. This problem has been studied before, but the state-of-the-art is still not efficient enough. In this paper, we propose an efficient algorithm for the optimal location query problem, which is based on a novel idea of \emph{nearest location component}. We also discuss three extensions of the optimal location query problem, namely the optimal multiple-location query problem, the optimal location query problem on 3D road networks, and the optimal location query problem with another objective. Extensive experiments were conducted which showed 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, on our largest real datasets, the state-of-the-art ran for more than 10 hours but our algorithm ran within 3 minutes only (i.e., >200 times faster).
Original languageEnglish
Title of host publicationProceedings of the 2014 ACM SIGMOD International Conference on Management of Data
Place of PublicationSnowbird, USA
PublisherAssociation for Computing Machinery
Number of pages12
ISBN (Electronic)978-1-4503-2376-5
Publication statusPublished - 2014
Externally publishedYes


Dive into the research topics of 'Efficient algorithms for optimal location queries in road networks'. Together they form a unique fingerprint.

Cite this