计算机工程
計算機工程
계산궤공정
COMPUTER ENGINEERING
2013年
7期
26-30,44
,共6页
最近邻%受限网络%移动对象%概率最近邻%概率Voronoi图%R+树
最近鄰%受限網絡%移動對象%概率最近鄰%概率Voronoi圖%R+樹
최근린%수한망락%이동대상%개솔최근린%개솔Voronoi도%R+수
Nearest Neighbor(NN)%constrained network%moving object%Probabilistic Nearest Neighbor(PNN)%probabilistic Voronoi diagram%R+tree
基于自由空间移动对象概率最近邻查询,给出受限网络移动对象概率最近邻(CNPNN)查询概念,提出一种基于网络概率Voronoi 图的 CNPNN 查询算法。利用基于网络距离的概率度量得到不确定数据的网络概率 Voronoi 单元,建立网络概率 Voronoi图覆盖受限网络。使用对点查询具有优势的 R+树,对不确定数据的网络概率 Voronoi 单元进行索引,减少搜索时间。确定查询对象所在网络Voronoi单元,得到查询对象最可能的最近邻。实验结果表明,该算法时间复杂度为O(n2+mlogmn),在一定条件下具有较好的性能。
基于自由空間移動對象概率最近鄰查詢,給齣受限網絡移動對象概率最近鄰(CNPNN)查詢概唸,提齣一種基于網絡概率Voronoi 圖的 CNPNN 查詢算法。利用基于網絡距離的概率度量得到不確定數據的網絡概率 Voronoi 單元,建立網絡概率 Voronoi圖覆蓋受限網絡。使用對點查詢具有優勢的 R+樹,對不確定數據的網絡概率 Voronoi 單元進行索引,減少搜索時間。確定查詢對象所在網絡Voronoi單元,得到查詢對象最可能的最近鄰。實驗結果錶明,該算法時間複雜度為O(n2+mlogmn),在一定條件下具有較好的性能。
기우자유공간이동대상개솔최근린사순,급출수한망락이동대상개솔최근린(CNPNN)사순개념,제출일충기우망락개솔Voronoi 도적 CNPNN 사순산법。이용기우망락거리적개솔도량득도불학정수거적망락개솔 Voronoi 단원,건립망락개솔 Voronoi도복개수한망락。사용대점사순구유우세적 R+수,대불학정수거적망락개솔 Voronoi 단원진행색인,감소수색시간。학정사순대상소재망락Voronoi단원,득도사순대상최가능적최근린。실험결과표명,해산법시간복잡도위O(n2+mlogmn),재일정조건하구유교호적성능。
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.