Download PDFOpen PDF in browserProbabilistic Maximum RangeSum Queries on Spatial Database (technical report)EasyChair Preprint no. 117514 pages•Date: June 12, 2019AbstractMaximum RangeSum (MaxRS) query is an important operator in spatial databases for retrieving regions of interest (ROIs). Given a rectangular query size $a\times b$ and a set of spatial objects associated with positive weights, MaxRS retrieves rectangular regions $Q$ of size $a\times b$, such that the sum of object weights covered by $Q$ (i.e., rangesum) is maximized. Due to the inaccuracy of the location acquisition, the collected locations of spatial objects are inherently uncertain and imprecise, which can be modeled by uncertain objects. In this paper, we propose a Probabilistic Maximum RangeSum (PMaxRS) query over uncertain spatial objects, which obtains a set $\gamma^*$ of rectangles such that the probability that each region $Q\in\gamma^*$ has the maximum rangesum exceeds a userspecified threshold $P_t$. We show that determining whether a given region $Q$ is in the answer of PMaxRS query is as hard as the #KNAPSACK problem, which is the counting version of the classic KNAPSACK problem and has already been proved as #Pcomplete. Thus, we put forward an efficient PMaxRS\_Framework based on pruning and refinement strategies. In the pruning step, we propose a candidate generation technique to reduce the search space. In the refinement step, we design an efficient samplingbased algorithm to verify the remaining candidate regions. Extensive experiments on several datasets are conducted to demonstrate the effectiveness and efficiency of our algorithms. Furthermore, we show that our PMaxRS\_Framework can be easily extended to answer top$k$ PMaxRS query and PMaxCRS, a variant of the PMaxRS query with circular shapes. Keyphrases: approximate algorithm, computational geometry, probabilistic database, Spatial Query Processing
