关键词: 空间数据库, 反向最远邻查询, 离散边界点, 半平面修剪策略, 四分邻域区

Abstract:

At present, most of reverse furthest neighbor (RFN) query methods do not judge whether the query point has a result set, so even when a RFN result set does not exist, all the operations are still done and time is vainly consumed. To effectively deal with the RFN query problems, we propose a method in which whether the query point having a RFN result set is judged by discrete boundary points. Discrete boundary points, four neighborhood areas and half space trimming strategy are employed to do the filtering, and then the result set obtained by the filtering is verified. The impact of the position of the query point, the size of data sets and data distribution on queries is tested, which is also compared with that of the judging method using convex. Experimental results show that when the query point is not a discrete boundary point, the time consumption for queries is almost zero; but when the query point is a discrete boundary point, the time consumption increases, which demonstrates that the proposed method is effective and can get the RFN results set.

Key words: spatial database, reverse furthest neighbors query, discrete boundary points, half-space trimming strategy, four neighborhood areas