摘要： 针对网络空间中有范围约束、不确定对象的最近邻查询问题，提出范围受限的网络空间模糊对象最近邻查询概念，并根据查询顺序的不同，给出NN-R查询算法和R-NN查询算法。两种算法均采用网络位置信息与连接信息分别存储的方式，使用聚类文件进行组织，减少I/O操作。NN-R算法在近邻查询过程中利用查询对象与受限范围的α-距离作为约束，缩小搜索范围。R-NN算法将受限范围内查询对象的欧氏近邻作为候选对象，利用欧氏距离的下界性与易求性降低时间复杂度。两种算法时间复杂度分别为O((logm1|E|+(|V*|m3+1)logm2|V|+|E|+|V|log|V|+n(lgn+1))和O(logm4n+(k+1)logm1|E|+|E|+|V|log|V|)。实验结果表明，在各自适用条件下，两种算法均有较好的性能。

关键词: 确定网络, 范围约束, 模糊最近邻, α-距离, 邻接表, R树

Abstract: Aiming at nearest neighbor query for uncertain object with range constraint in network, the concept of nearest neighbor query for fuzzy object in constraint network is put forward. According to the query sequence, two query algorithms are proposed: NN-R and R-NN. In the way of storage, the two algorithms all use the index structure that spatial location information separated from network space connection information, and they use clustering file organization to reduce I/O operation. NN-R algorithm reduces the search area by using minimum and maximum α-distance between fuzzy object and range constraint. R-NN algorithm uses Euclidean nearest neighbors as the candidates. It declines the complexity by using that Euclidean distance can be computed easily and is the bottom boundary of the network distance. The complexity of the algorithms is respectively O((logm1|E|+(|V*|m3+1)logm2|V|+|E|+|V|log|V|+n(lgn+1)) and O(logm4n+ (k+1)logm1|E|+|E|+|V|log|V|). Experimental results show that the two algorithms all have better performance in the condition of their own applied area.

Key words: certain network, range constraint, fuzzy nearest neighbor, α-distance, adjacent table, R tree

中图分类号: 

• TP311.13