A Probabilistic Approach for GNN Queries in LBS

Range-based Probabilistic Group Nearest Neighbor (in short RP-GNN) query has recently gain much attention, due to its wide usage in many Location Based Services (LBSs). Previous works mainly focus on the uncertainty of data objects (P). While the uncertainty of query objects (Q) is prevailing in reality. In this paper, a comprehensive discussion on uncertain query objects is presented. Meanwhile two novel pruning methods are proposed to improve the performance of RP-GNN: one is Query points pruning (Q_pruning) and the other is Geometric pruning (G_pruning). Q_pruning reduces the number of query objects needed to be considered. And G_pruning method exploits the geometric properties of the RP-GNN problem to narrow down the search space. Extensive experiments show the effectiveness, efficiency and scalability of proposed methods