受限网络模糊对陥最近邻查询

摘要：

针对网络空间中有范围约束、不确定对象的最近邻查询问题，提出范围受限的网络空间模糊对象最近邻查询概念，并根据查询顺序的不同，给出 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树

分类号：TP311.13(计算技术、计算机技术)

资助基金：黑龙江省自然科学基金资助项目F200821。

在线出版日期：2014-04-15（万方平台首次上网日期，不代表论文的发表时间）

页数：共7页

页码：39-45