A Branch and Bound Method for Min-dist Location Selection Queries

Qi, J., Xu, Z., Xue, Y. and Wen, Z.

    Given a set of clients and a set of existing facilities, the min-dist location selection query returns a location from a given set of potential locations for establishing a new facility so that the average distance between a client and her nearest facility is minimized. This type of queries has a wide range of applications in marketing, decision support systems, urban development simulations and massively multiplayer online games. The computational cost of a naive algorithm, which sequentially scans all the potential locations, is too high to process this type of queries in real time. Motivated by this, we propose a branch and bound algorithm that exploits geometric properties of the data objects and early prunes unpromising potential locations from consideration to achieve a higher query processing efficiency. We conduct a detailed cost analysis and extensive experiments to validate the efficiency of the branch and bound algorithm. The results show that the proposed algorithm outperforms the naive algorithm constantly.
Cite as: Qi, J., Xu, Z., Xue, Y. and Wen, Z. (2012). A Branch and Bound Method for Min-dist Location Selection Queries. In Proc. Australasian Database Conference (ADC 2012) Melbourne, Australia. CRPIT, 124. Zhang, R. and Zhang, Y. Eds., ACS. 51-60
pdf (from crpit.com) pdf (local if available) BibTeX EndNote GS