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

A Space Trimming Method for Continuous Reverse Nearest Neighbor Search

作　　者：高峰[1] 赵丹枫[1] 刘国华[1] 刘军生[2] 张奇[1] 张宇[1] 

机构地区：[1]燕山大学信息科学与工程学院,河北秦皇岛066004 [2]燕山大学软件中心,河北秦皇岛066004

出　　处：《计算机工程与科学》2007年第10期32-34,37,共4页Computer Engineering & Science

基　　金：教育部科学技术研究重点项目(205014)

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

关 键 词：削减空间 连续 反最近邻 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]