  Facility location queries identify the best locations to set up new
facilities for providing service to its users. Majority of the existing works
in this space assume that the user locations are static. Such limitations are
too restrictive for planning many modern real-life services such as fuel
stations, ATMs, convenience stores, cellphone base-stations, etc. that are
widely accessed by mobile users. The placement of such services should,
therefore, factor in the mobility patterns or trajectories of the users rather
than simply their static locations. In this work, we introduce the TOPS
(Trajectory-Aware Optimal Placement of Services) query that locates the best k
sites on a road network. The aim is to optimize a wide class of objective
functions defined over the user trajectories. We show that the problem is
NP-hard and even the greedy heuristic with an approximation bound of (1-1/e)
fails to scale on urban-scale datasets. To overcome this challenge, we develop
a multi-resolution clustering based indexing framework called NetClus.
Empirical studies on real road network trajectory datasets show that NetClus
offers solutions that are comparable in terms of quality with those of the
greedy heuristic, while having practical response times and low memory
footprints. Additionally, the NetClus framework can absorb dynamic updates in
mobility patterns, handle constraints such as site-costs and capacity, and
existing services, thereby providing an effective solution for modern
urban-scale scenarios.
