Place Your Next Branch with MILE-RUN: Min-dist Location Selection over User Movement

Due to the wide spectrum of applications, the Min-dist location selection problem has drawn much research attention in spatial database studies. Given a group of existing locations of a specific kind of facility, Min-dist problem aims to find the optimal location from series of candidate places to establish a new facility such that the average distance between users and their respective nearest facilities can be minimized. Although plenty of efforts have been proposed to address Min-dist problems, they all assume that users are stationary. Unfortunately, in practice, objects (e.g., people, animals) are mobile in various scenarios. Due to the movements of users, it is non-trivial to identify an optimal candidate, where none of existing solutions is applicable. Motivated by that, in this paper we take into account the mobile factor and present the first effort on a generalized Min-dist problem, called Min-dIst Location SElection oveR User MovemeNt (mile-run). To address the efficiency issue caused by user movement and road network, based on a reference location transformation, we present two groups of algorithms, index-based and index-free ones. The first group answers mile-run efficiently with the help of spatial locality based index structures, and fits the case where facilities and users are known apriori, while the second group solves the problem from scratch. Extensive experiments are conducted on both real-world and synthetic datasets, the results of which demonstrate that our algorithms are more efficient compared to the baseline method by orders of magnitude.