摘要: 针对位置服务应用中,基于道路网络的移动对象连续K最近邻(CKNN)查询实时响应速度慢的问题,提出基于方向关系约束的移动对象CKNN查询算法CDR-CKNN。采用锥形模型建立方向关系表示模型,将查询中的方向关系谓词转化为开放图形,作为K最近邻查询的约束条件,快速过滤与查询结果无关的道路边,从而避免查找最近邻对象时对道路网的盲目扩展,缩短查找K最近邻对象的时间。实验结果表明,当道路网络规模增加时,CDR-CKNN算法查询性能比IMA/GMA算法提高2倍~3.3倍,其性能受兴趣点对象分布密度影响较小;采用八方向锥形模型比四方向锥形模型的算法查询效率提高1.5倍~3倍。
关键词:
方向关系模型,
方向关系谓词,
道路网络,
连续K最近邻查询,
开放图形,
锥形模型
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.
Key words:
directional relation model,
directional relation predicate,
road network,
Continuous K Nearest Neighbors(CKNN) query,
open shape,
cone model
中图分类号:
孙海龙,王霓虹,王春艳. 道路网络中基于方向关系约束的CKNN查询[J]. 计算机工程, 2014, 40(12): 50-56.
SUN Hailong,WANG Nihong,WANG Chunyan. CKNN Query Based on Constraint of Directional Relation in Road Network[J]. Computer Engineering, 2014, 40(12): 50-56.