道路网络中基于方向关系约束的CKNN查询  

CKNN Query Based on Constraint of Directional Relation in Road Network

作　　者：孙海龙[1] 王霓虹[1] 王春艳[2] 

机构地区：[1]东北林业大学信息与计算机工程学院,哈尔滨150040 [2]东北林业大学图书馆,哈尔滨150040

出　　处：《计算机工程》2014年第12期50-56,共7页Computer Engineering

基　　金：中央高校基本科研业务费专项基金资助项目(DL12AB02);国家"863"计划基金资助项目(2012AA102003-2);国家林业局公益性行业科研专项基金资助项目(201104037)

摘　　要：针对位置服务应用中，基于道路网络的移动对象连续K最近邻（ CKNN ）查询实时响应速度慢的问题，提出基于方向关系约束的移动对象CKNN查询算法CDR-CKNN。采用锥形模型建立方向关系表示模型，将查询中的方向关系谓词转化为开放图形，作为K最近邻查询的约束条件，快速过滤与查询结果无关的道路边，从而避免查找最近邻对象时对道路网的盲目扩展，缩短查找K最近邻对象的时间。实验结果表明，当道路网络规模增加时， CDR-CKNN算法查询性能比IMA/GMA算法提高2倍~3.3倍，其性能受兴趣点对象分布密度影响较小；采用八方向锥形模型比四方向锥形模型的算法查询效率提高1.5倍~3倍。Aiming at the problem that the real-time response of Continuous K Nearest Neighbors（ CKNN） query in road networks is slow in location based services,this paper proposes a CKNN query based on constraint of directional relation, named CDR-CKNN. The algorithm takes the cone-based model as directional relation model, converts the directional relation predicate into open shape which is the constraint condition of K Nearest Neighbor（ KNN） query,and pruns the irrelevant road network edges with query result. It avoids blind network expansion,and decreases the time of finding out KNN. Experimental results show that CDR-CKNN algorithm has better query performance than classical IMA/GMA algorithm when road network becomes larger, the performance is increased by 2 ~3. 3 times, moreover, distribution density of Points of Interest （ POI ） has fewer influence on CDR-CKNN than IMA/GMA. Simultaneously, the query efficiency based on eight-direction cone model is increased by 1. 5~3 times than four-direction cone model.

关 键 词：方向关系模型 方向关系谓词 道路网络 连续K最近邻查询 开放图形 锥形模型 

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