计算机工程Issue(12)：50-56,7.DOI:10.3969/j.issn.1000-3428.2014.12.009
道路网络中基于方向关系约束的CKNN查询
CKNN Query Based on Constraint of Directional Relation in Road Network
摘要
Abstract
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最近邻查询/开放图形/锥形模型Key words
directional relation model/directional relation predicate/road network/Continuous K Nearest Neighbors ( CKNN) query/open shape/cone model分类
信息技术与安全科学引用本文复制引用
孙海龙,王霓虹,王春艳..道路网络中基于方向关系约束的CKNN查询[J].计算机工程,2014,(12):50-56,7.基金项目
中央高校基本科研业务费专项基金资助项目(DL12AB02) （DL12AB02）
国家“863”计划基金资助项目(2012AA102003-2) （2012AA102003-2）
国家林业局公益性行业科研专项基金资助项目(201104037)。 （201104037）
