Conference Proceedings

A branch and bound method for min-dist location selection queries

J Qi, Z Xu, Y Xue, Z Wen

Proceedings of the Twenty-Third Australasian Database Conference | Australian Computer Society | Published : 2012


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 ob..

View full abstract

Citation metrics