一种用于连续反最近邻查询的空间削减算法

动态环境中的反最近邻查询已成为空间查询的研究热点,有效的数据空间削减策略是此类查询的瓶颈。本文首先给出了连续反最近邻CRNN查询的定义,并且深入分析了问题的特点;其次,在综合分析已有削减策略的基础上给出了可用于CRNN查询的空间削减算法。该算法能在降低I/O操作的同时保证结果的精确性,并且不依赖于特定的索引结构和查询算算法。实验表明,该算法能够有效削减掉不包含RNN的结点,能够提高CRNN查询效率。

A Space Trimming Method for Continuous Reverse Nearest Neighbor Search

The reverse nearest neighbor search in dynamic environments is becoming a hot topic, and an efficient space trimming method is the bottleneck of such a search. First, a formal definition of CRNN is given and a deep analysis of the problem is followed. Second, based on the analysis of the existing trimming methods, the paper presents a novel space-trimming algorithm, which can be applied to continuous reverse nearest neighbor search. The algorithm can reduce I/O access efficiently and guarantee the precision of the result. In addition, it does not rely on specific indices or search algorithms. Experiments show that the algorithm can efficiently eliminate the nodes which do not contain true RNNs and hence improve the efficiency of CRNN search.