摘要：

基于自由空间移动对象概率最近邻查询，给出受限网络移动对象概率最近邻(CNPNN)查询概念，提出一种基于网络概率Voronoi图的CNPNN查询算法。利用基于网络距离的概率度量得到不确定数据的网络概率Voronoi单元，建立网络概率Voronoi图覆盖受限网络。使用对点查询具有优势的R+树，对不确定数据的网络概率Voronoi单元进行索引，减少搜索时间。确定查询对象所在网络Voronoi单元，得到查询对象最可能的最近邻。实验结果表明，该算法时间复杂度为O(n2+mlogmn)，在一定条件下具有较好的性能。

关键词: 最近邻, 受限网络, 移动对象, 概率最近邻, 概率Voronoi图, R+树

Abstract:

Based on moving object probabilistic nearest neighbor query in free space, the concept of constrained network moving object Probabilistic Nearest Neighbor query(CNPNN) is put forward, and the CNPNN algorithm based on network probabilistic Voronoi diagram is proposed. The probabilistic measure based on the network distance is used to derive the network probabilistic Voronoi cells of the uncertain objects, and the network probabilistic Voronoi diagram is built to cover the constrained network. R+ tree is used to index network probabilistic Voronoi cells for decreasing search time. Network probabilistic Voronoi cell containing query object is located to acquire query object’s most likely Nearest Neighbor(NN). Experimental results show that the time complexity of algorithm is O(n2+mlogmn), has a better performance under certain conditions.

Key words: Nearest Neighbor(NN), constrained network, moving object, Probabilistic Nearest Neighbor(PNN), probabilistic Voronoi diagram, R+ tree

中图分类号: 

• TP311