Approximate maxrs in spatial databases
Publication in refereed journal

Times Cited
Altmetrics Information

Other information
AbstractIn the maximizing range sum (MaxRS) problem, given (i) a set P of 2D points each of which is associated with a positive weight, and (ii) a rectangle r of specific extents, we need to decide where to place r in order to maximize the covered weight of r - that is, the total weight of the data points covered by r. 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* where m* 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. © VLDB Endowment.
All Author(s) ListTao Y., Hu X., Choi D., Chung C.
Journal nameProceedings of the VLDB Endowment
Volume Number6
Issue Number13
Pages1546 - 1557
LanguagesEnglish-United Kingdom

Last updated on 2020-04-12 at 00:02