An Index-Based Method for Efficient Maximizing Range Sum Queries in Road Network

Given a set of positive weighted points, the Maximizing Range Sum (maxRS) problem finds the placement of a query region r of given size such that the weight sum of points covered by r is maximized. This problem has long been studied since its wide application in spatial data mining, facility locating, and clustering problems. However, most of the existing work focus on Euclidean space, which is not applicable in many real-life cases. For example, in location-based services, the spatial data points can only be accessed by following certain underlying (road) network, rather than straight-line access. Thus in this paper, we study the maxRS problem with road network constraint, and propose an index-based method that solves the online queries highly efficiently.