道路网络中基于RRN-Tree的移动对象CKNN查询方法

摘要

道路网络中基于RRN-Tree的移动对象CKNN查询方法，涉及一种数据查询方法。为了解决现有采用索引结构对道路网络段进行索引，将道路网络建模为有向/无向图，基于内存数据结构处理最近邻查询请求，但是当道路网络数据量较大、路段较多时，查询效率急剧降低；并且，基于图的建模方式，无法反映出移动对象在路口的转向关系，无法解决具有路口转向和U型转弯约束的复杂道路网络最近邻查询的问题。它提出RRN-Tree索引结构，对道路网络及兴趣点对象进行索引，同时在索引结构中为路径上的交叉点建立邻接链表，存储路口处各路段之间的连接关系，从而完成复杂约束条件下道路网络CKNN查询。用于道路网络CKNN查询。

主权项

道路网络中基于RRN‑Tree的移动对象CKNN查询方法，其特征在于：该查询方法的实现步骤为：步骤一：首先，分别定义道路网络G、路线r、路段seg、交叉路口j、移动对象o和KNN监测区；所述道路网络G为一个二元组G＝(R，J)，其中R是道路网中路线集合，每条路线包含若干路段，J是道路网中多条路线的交叉点集合；所述路线r是指道路网络中可独立命名的一条完整路径，定义为：$r=(rid,len,{\left({\mathrm{jid}}_j,{\mathrm{pos}}_j\right)}_{j=1}^m);$其中，rid是路线标识；len表示路线长度，len∈[0,1]；表示路线上的交叉路口及其在路线上相对路线起点的位置集合，pos_j∈[0,1]；所述路段seg是指相邻交叉路口之间的一段路线，定义为：seg＝(sid,rid,p_s,p_e,dir)；其中，sid、rid分别表示路段及所在路线的标识；p_s、p_e表示路段的起始点和终点；dir∈{‑1,0,1}，当值为1时表示移动对象在该路段上允许从起点向终点方向运动，值为‑1则表示从路段终点向起始点方向运动，0表示该路段允许双向通行；所述交叉路口j是指多条路线的交叉节点，定义为：其中jid为交叉路口的标识；(rid_j,pos_j)表示该交叉路口在第j条路线上的位置；adjList为交叉路口的邻接列表，存储该交叉路口处各路段的连接关系；所述移动对象o是指在道路网络中，将移动对象o建模为：o＝(oid,x,y,rid,pos,dir')；其中，oid、rid分别表示移动对象标识及其所在路线标识；x，y表示移动对象的经纬度坐标；pos表示移动对象距离所在路线起点的距离，pos∈[0,1]；dir'表示移动对象的运行方向，值为1表示从所在路段起点向终点方向运行，值为‑1则是从所在路段的终点向起点方向运行；所述KNN监测区是指以查询对象q为根，KNN_dist为距离上限，所有与q相连的路段构成的查询区域；步骤二、构建RRN‑Tree索引结构，将邻接链表技术引入索引结构中，用邻接链表来表示路线上交叉路口处的道路边之间的连接关系，基于网络边扩展思想，计算查询对象的K个最近邻对象；同时在计算KNN查询结果集时建立K近邻监测区；所述RRN‑Tree索引结构由三部分组成：对道路网络的路线进行索引的顶层2D R‑Tree、表示路线上交叉节点邻接关系的邻接链表和索引各个路线上移动对象的底层R‑Tree；所述对道路网络的路线进行索引的顶层2D R‑Tree，其叶子节点是一个三元组：<mbb,polypt,treept>；其中，mbb表示路线对应polyline的最小外包边界；polypt指向路线的实际表示，treept指向底层R树；所述索引各个路线上移动对象的底层R‑Tree，其叶子节点是一个二元组：<mbb',childpt>，其中mbb'表示所有孩子节点的MBBs集合，childpt指向孩子节点，即：索引某路线对应的各路段及路段上的移动对象的底层R树指针；所述表示路线上交叉节点邻接关系的邻接链表是由hash表和两级单链表组成，hash表部分与MON‑Tree中含义相同，第一级单链表表示路线上的各个节点，第二级节点表示某节点的出度；步骤三：根据步骤二所构建的RRN‑Tree索引结构，进行基于道路网络的CKNN查询；所述基于道路网络的CKNN查询包括KNN查询初始集计算和CKNN查询更新两个阶段：首先，第一阶段所述KNN查询初始集计算是指：当查询对象基于当前位置发出KNN查询请求时，首先通过RRN‑Tree索引结构快速定位查询对象所在路段，并将路段的两个端点入队列，并按照距离查询点的距离从小到大排序；然后读取距离查询点最近的兴趣点对象存入结果队列中，当对象数少于K个时，沿着查询对象前进方向的路段顶点继续扩展，通过读取路段顶点的邻接链表确定各路段的连接关系，在有连接关系的路段上扩展查找最近邻对象，直到找到K个对象为止；最后，为了提高连续查询的查询效率，以第K个对象距离查询点的距离为距离上限，将所有与查询点有连接关系的路段建立KNN查询监测区，凡是落在该监测区域内的对象将成为候选的KNN结果；第二阶段进行CKNN查询更新，所述CKNN查询更新分为两种情况：当查询点对象位置不变，而兴趣点对象移动时，利用查询过程生成的KNN监测区可降低查询更新代价；当查询点对象移动时，应用上述的第一阶段的KNN查询初始集计算的查询算法重新计算查询请求。