Rotating MaxRS queries

Given a set of weighted objects in a data space, the MaxRS problem in spatial databases studied in a VLDB 2012 paper is to find a location for a rectangular region of a given size such that the weighted sum of all the objects covered by the rectangular region centered at the optimal location is maximized. This problem is useful in lots of location-based service applications, such as finding the location for a new fast food restaurant with a limited delivery range attracting the greatest number of customers. The existing MaxRS problem assumes that the rectangular region is always placed horizontally and is non-rotatable. However, under this assumption, the weighted sum of all the covered objects may not be the greatest when the rectangular region is rotatable. In this paper, we propose a generalized MaxRS problem called rotating MaxRS without this assumption. In rotating MaxRS, the rectangular region is rotatable and can be associated with an inclination angle. The goal of our problem is to find a location and an inclination angle such that the weighted sum of all the objects covered by the rectangular region of a given size centered at this location with this inclination angle is the greatest. We also present an efficient algorithm for the problem. Extensive experiments were conducted to verify the efficiency of our algorithms based on the real and synthetic datasets. The experimental results show that the weighted sum of all the objects in the rotating MaxRS queries can be increased with up to 300% on the synthetic datasets compared with existing non-rotating MaxRS queries, which shows the significance of the new rotating MaxRS queries.