Approximate MaxRS in spatial databases
Yufei Tao, Xiaocheng Hu, Dong-Wan Choi, Chin‐Wan Chung · Proceedings of the VLDB Endowment · 2013
In the maximizing range sum (MaxRS) problem, given (i) a setPof 2D points each of which is associated with a positive weight, and (ii) a rectanglerof specific extents, we need to decide where to placerin order to maximize the covered weight ofr- that is, the total weight of the data points covered byr. Algorithms solving the problem exactly entail expensive CPU or I/O cost. In practice, exact answers are often not compulsory in a MaxRS application, where slight imprecision can often be comfortably tolerated, provided that approximate answers can be computed considerably faster. Motivated by this, the present paper studies the (1 - ε)-approximate MaxRS problem, which admits the same inputs as MaxRS, but aims instead to return a rectangle whose covered weight is at least (1-ε)m*, wherem* is the optimal covered weight, and ε can be an arbitrarily small constant between 0 and 1. We present fast algorithms that settle this problem with strong theoretical guarantees.