道路网中基于RRN-Tree的CKNN查询

CKNN Query Based on RRN-Tree in Road Network

现有针对基于道路网络的CKNN查询研究，主要是将道路网络以路段和节点的形式进行建模，转化成基于内存的有向／无向图，该模型存在2个问题：一个是道路网络中路段数据量大，导致索引结构分支过多、移动对象更新频繁；另一个是图表示方法不能很好地处理十字路口转向、U型转弯等交通规则。针对此问题，提出道路网中基于RRN—Tree的移动对象CKNN查询算法，包括索引结构设计和移动对象查询算法设计，采用路线对道路网建模，基于网络边扩展方式，实现复杂条件下的道路网络CKNN查询。实验结果表明，在各种网络密度和兴趣点对象分布密度下，与经典的IMA／GMA算法相比，基于RRN—Tree索引方法的查询性能提高1．5倍-2．13倍。

Most of existing methods for Continuous K Nearest Neighbors（CKNN） query of moving objects in road networks model the road networks as road segments and nodes, and convert them into directional graph or undirectional graph in memory. There are two problems with this model. First, the number of road segments is so huge that there are too many branches in index structure and frequent update of moving objects. Second, traffic regulations like the crossroads turn and U turn cannot be processed in graph model. This paper proposes a CKNN query algorithm of moving objects based on RRN-Tree in road networks, which includes the design of index structure and query algorithm for moving objects, models road network as routes, and implements CKNN query in road networks under complicated road conditions by expanding the road edges. Experimental results show that the method based on RRN-Tree has better query performance than classical IMA/GMA algorithm under various network density and objects distribution density, and the performance is increased by 1.5-2.13 times.