  This paper investigates the MaxRS problem in spatial databases. Given a set O
of weighted points and a rectangular region r of a given size, the goal of the
MaxRS problem is to find a location of r such that the sum of the weights of
all the points covered by r is maximized. This problem is useful in many
location-based applications such as finding the best place for a new franchise
store with a limited delivery range and finding the most attractive place for a
tourist with a limited reachable range. However, the problem has been studied
mainly in theory, particularly, in computational geometry. The existing
algorithms from the computational geometry community are in-memory algorithms
which do not guarantee the scalability. In this paper, we propose a scalable
external-memory algorithm (ExactMaxRS) for the MaxRS problem, which is optimal
in terms of the I/O complexity. Furthermore, we propose an approximation
algorithm (ApproxMaxCRS) for the MaxCRS problem that is a circle version of the
MaxRS problem. We prove the correctness and optimality of the ExactMaxRS
algorithm along with the approximation bound of the ApproxMaxCRS algorithm.
From extensive experimental results, we show that the ExactMaxRS algorithm is
two orders of magnitude faster than methods adapted from existing algorithms,
and the approximation bound in practice is much better than the theoretical
bound of the ApproxMaxCRS algorithm.
