Probabilistic Maximum Range-Sum Queries on Spatial Database (technical report)

EasyChair Preprint 1175

Abstract

Maximum Range-Sum (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., range-sum) 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 Range-Sum (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 range-sum exceeds a user-specified 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 #P-complete. 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 sampling-based 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: Spatial Query Processing, approximate algorithm, computational geometry, probabilistic database

@booklet{EasyChair:1175,
  author    = {Qiyu Liu and Xiang Lian and Lei Chen},
  title     = {Probabilistic Maximum Range-Sum Queries on Spatial Database (technical report)},
  howpublished = {EasyChair Preprint 1175},
  year      = {EasyChair, 2019}}