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

摘要

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

说明书

技术领域

本发明涉及一种数据查询方法。

背景技术

随着无线通信技术的发展和具有GPS定位功能的移动电话、PDA等便携设备的普及， 基于位置服务（LBS，Location Based Service）得以快速发展，已广泛应用于地理信息 系统、应急服务、汽车导航和旅游路径规划等领域。空间查询与基于位置服务密切相关， 其中基于道路网络的移动对象连续K最近邻查询（CKNN，Continouns K Nearest Neighbors） 就是一类重要的查询请求，能够在道路网络环境下不断查找距离给定查询对象最近的K 个最近邻目标，例如，在消防指挥中，查找距离指挥中心最近的4辆消防车。解决此类问 题的关键在于：1）快速实时计算任意两个移动对象之间的最短路径；2）移动对象位置更 新的维护与管理。

国内外针对道路网络的CKNN查询问题，学者们做了一些工作。Kolahdouzan提出 IE/UBA方法，利用Voronoi图处理网络空间的CNN问题，通过减少查询路径上的KNN计 算次数提高算法效率，但当K值增大、对象分布密度增加时，算法效率急剧下降。Cho针 对IE/UBA方法中查询性能受对象分布密度影响提出UNICONS技术，充分利用预计算汇聚 节点（Condensing Point）的最近邻提高最短路径计算速度；为完成CKNN查询，将查询 路径分成若干子段，快照式计算每个子段端点的KNNs，每个端点的KNNs及子段上的对象 构成最终查询结果。以上方法都是研究查询对象是移动而兴趣点对象是静止的情况。 Mouratidis^[3]提出IMA/GMA方法处理查询对象和兴趣点对象在道路网上任意移动的CKNN 查询问题。该算法是目前公认的处理基于道路网络的CKNN查询经典算法，系统采用基于 内存的数据结构存储网络边、节点以及查询信息，提出IMA/GMA算法处理查询请求。IMA 算法从查询对象所在边开始扩展网络边，并遍历网络边上的兴趣点对象，形成初始KNNs 查询结果集，同时以查询点为根，建立查询扩展树，处理查询请求、移动对象和道路边权 重更新时的连续查询请求；GMA采用IMA和共享执行机制，算法的核心是称作序列 （Seqence）的概念，即：序列上的查询请求结果为序列上的对象和序列端点处KNNs结果 的并集，当多个查询请求处在同一序列上时可共享已获得的查询结果。为了维护查询结果 的更新，在计算初始KNNs时建立影响列表。IMA/GMA方法采用基于内存的方式存储网络 及移动对象，不适合大型道路网络。Wang提出MovNet框架处理道路网络环境下的基于位 置的查询，使用基于磁盘的R树索引道路网络，基于内存的格网索引管理移动对象的位置 更新，通过网格重叠计算算法将道路网与格网单元进行关联，完成基于位置的范围查询和 KNN查询。Demisyurek针对IMA/GMA算法使用Dijkstra算法网络距离计算时盲目扩展以 及对象位置更新时盲目映像的缺点，提出ER-CKNN算法，基于PMR-QuadTree索引道路网 络，基于格网索引管理移动对象位置更新，使用称作edge-bitmap-encoding技术结合A* 启发式搜索算法，提高最短路径计算速度；同时，在查询时使用欧式距离约束（Euclidean  Restriction）限制K近邻搜索区域；对象位置更新时，只对区域内的移动对象进行更新， 从而加快查询处理速度。廖巍[6]针对基于道路网络的CKNN查询处理,提出一种新的道路 网络有向图模型,分别利用基于内存的哈希表和线性链表结构对移动对象当前位置和道 路网络有向图模型进行存储和管理.通过引入单向网络距离度量和双向网络距离度量,提 出单向网络扩展(UNE)算法和双向网络扩展(BNE)算法以支持不同语义的连续k近邻查 询处理，并采用影响树及网络扩展策略来减少连续k近邻查询更新的搜索代价。赵亮[7] 针对数据频繁更新时查询性能下降问题，结合多核多线程技术，提出了一种基于多线程的 连续查询处理框架。该框架周期性重计算所有查询结果，将查询处理分为顺序执行的数据 更新阶段和查询执行阶段，分别使用任务并行和数据并行的方法执行各阶段的操作。设计 了数据更新阶段使用的数据结构，提出了查询处理阶段的k近邻查询处理策略，包含离 线预计算和在线k近邻查询处理算法两个部分，并对k近邻算法复杂性及多线程处理框架 的加速比进行了理论分析。

然而，以上文献都是采用一种索引结构对道路网络段进行索引，将道路网络建模为有 向/无向图，基于内存数据结构处理最近邻查询请求，但是当道路网络数据量较大、路段 较多时，查询效率急剧降低；并且，基于图的建模方式，无法反映出移动对象在十字路口 的转向关系，无法解决具有十字路口转向和U型转弯约束的复杂道路网络最近邻查询问 题。

发明内容

本发明的目的是为了解决现有采用索引结构对道路网络段进行索引，将道路网络建 模为有向/无向图，基于内存数据结构处理最近邻查询请求，但是当道路网络数据量较大、 路段较多时，查询效率急剧降低；并且，基于图的建模方式，无法反映出移动对象在十字 路口的转向关系，无法解决具有十字路口转向和U型转弯约束的复杂道路网络最近邻查询 问题，提供一种道路网络中基于RRN-Tree的移动对象CKNN查询方法。

道路网络中基于RRN-Tree的移动对象CKNN查询方法，该查询方法的实现步骤为：

步骤一：首先，分别定义道路网络G、路线r、路段seg、交叉路口j、移动对象o 和KNN监测区；

所述道路网络G为一个二元组G=（R，J），其中R是道路网中路线集合，每条路线包 含若干路段，J是道路网中多条路线的交叉点集合；

所述路线r是指道路网络中可独立命名的一条完整路径，定义为：

$r=(\mathrm{rid},\mathrm{len},{({\mathrm{jid}}_j,{\mathrm{pos}}_j)}_{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查询初始集计算的的查询算法重新计算查询请 求。

本发明的优点是：

现有的研究基于道路网络的CKNN查询问题主要是将道路网络以路段和节点的形式进 行建模，转化成基于内存的有向/无向图，该模型存在两个问题：一是道路网络中路段数 据量大，导致索引结构分支过多、移动对象更新频繁；二是图表示方法不能很好地处理十 字路口转向、U型转弯等交通规则。针对此问题，基于路线对道路网络建模，提出一种新 的索引结构：RRN-Tree（Route based Road Networks Tree），基于网络边扩展方式，解 决复杂条件下的道路网络CKNN查询。实验结果表明，在各种网络密度和兴趣点对象分布 密度下，基于RRN-Tree索引方法的查询性能都优于经典的IMA/GMA算法，性能提高1.5～ 2.13倍。

附图说明

图1为基于路段的道路网络模型图；

图2为基于路线的道路网络模型图；

图3为具体实施方式一中所述的RRN-Tree索引结构中的对道路网络的路线（Route） 进行索引的顶层2D R-Tree和索引各个路线上移动对象的底层R-Tree；

图4为具体实施方式一中所述的RRN-Tree索引结构中的表示路线上交叉节点邻接关 系的邻接链表；

图5为单向行驶具有转向关系的道路网络模型图；

图6为以D_max为距离上限，查询点q为根，计算KNN监测区域的道路网络模型图；

图7为本发明所述的道路网络中基于RRN-Tree的移动对象CKNN查询方法和IMA/GMA 算法在LA道路网环境下POI对象数量及分布密度变化情况下的CPU响应时间对比情况； 随着POI对象数量增加，CPU响应时间明显下降，但是POI数量达到20K以上时，变化趋 于平缓，其中，代表IMA/GMA，代表本发明的方法；

图8为本发明所述的道路网络中基于RRN-Tree的移动对象CKNN查询方法和IMA/GMA 算法在SF道路网环境下POI对象数量及分布密度变化情况下的CPU响应时间对比情况；， 其中，代表IMA/GMA，代表本发明的方法；

图9：为本发明所述的道路网络中基于RRN-Tree的移动对象CKNN查询方法和IMA/GMA 算法在LA道路网络下POI分布密度对查询的影响，其中，代表IMA/GMA，代表本发明的方法；

图10为本发明所述的道路网络中基于RRN-Tree的移动对象CKNN查询方法和IMA/GMA 算法在SF道路网下POI分布密度对查询的影响，其中，代表IMA/GMA，代表本发明的方法；

图11为本发明所述的道路网络中基于RRN-Tree的移动对象CKNN查询方法和IMA/GMA 算法在SF道路网络环境下查询请求数k对查询性能的影响情况；从图中可以看出，随着 k值增加，CPU运行时间不断增加，但是本发明的方法的运行时间明显低于IMA/GMA算法 的运行时间；

图12为本发明所述的道路网络中基于RRN-Tree的移动对象CKNN查询方法和IMA/GMA 算法在LA道路网络环境下查询请求数k对查询性能的影响情况；从图中可以看出，随着 k值增加，CPU运行时间不断增加，但是本发明的方法的运行时间明显低于IMA/GMA算法 的运行时间。

具体实施方式

具体实施方式一：下面结合图1至图12说明本实施方式，本实施方式所述的道路网 络中基于RRN-Tree的移动对象CKNN查询方法，该查询方法的实现步骤为：

步骤一：首先，分别定义道路网络G、路线r、路段seg、交叉路口j、移动对象o 和KNN监测区；

所述道路网络G为一个二元组G=（R，J），其中R是道路网中路线集合，每条路线包 含若干路段，J是道路网中多条路线的交叉点集合；

所述路线r是指道路网络中可独立命名的一条完整路径，定义为：

$r=(\mathrm{rid},\mathrm{len},{({\mathrm{jid}}_j,{\mathrm{pos}}_j)}_{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（Route based Road Networks）索引结构，将邻接链表技术 引入索引结构中，用邻接链表来表示路线上交叉路口处的道路边之间的连接关系，基于网 络边扩展思想，计算查询对象的K个最近邻对象；同时在计算KNN查询结果集时建立K 近邻监测区；

所述RRN-Tree（Route based Road Networks）索引结构由三部分组成：对道路网络 的路线（Route）进行索引的顶层2D R-Tree、表示路线上交叉节点邻接关系的邻接链表 和索引各个路线上移动对象的底层R-Tree；

所述对道路网络的路线（Route）进行索引的顶层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（Route based Road Networks）索引结构， 进行基于道路网络的CKNN查询；

所述基于道路网络的CKNN查询包括KNN查询初始集计算和CKNN查询更新两个阶段：

首先，第一阶段所述KNN查询初始集计算是指：当查询对象基于当前位置发出KNN 查询请求时，首先通过RRN-Tree索引结构快速定位查询对象所在路段，并将路段的两个 端点入队列，并按照距离查询点的距离从小到大排序；然后读取距离查询点最近的兴趣点 对象存入结果队列中，当对象数少于K个时，沿着查询对象前进方向的路段顶点继续扩展， 通过读取路段顶点的邻接链表确定各路段的连接关系，在有连接关系的路段上扩展查找最 近邻对象，直到找到K个对象为止；最后，为了提高连续查询的查询效率，以第K个对象 距离查询点的距离为距离上限，将所有与查询点有连接关系的路段建立KNN查询监测区， 凡是落在该监测区域内的对象将成为候选的KNN结果；

第二阶段进行CKNN查询更新，所述CKNN查询更新分为两种情况：当查询点对象位置 不变，而兴趣点对象移动时，利用查询过程生成的KNN监测区可降低查询更新代价；当查 询点对象移动时，应用上述第一阶段的KNN查询初始集计算的的查询算法重新计算查询请 求。

具体实施方式二：下面结合图1至图12说明本实施方式，本实施方式为对实施方式 一的进一步说明，本实施方式所述的步骤三中所述的KNN查询初始集计算的具体实现过程 为：

首先，建立优先队列PQueue保存查询过程中的邻接点，该优先队列PQueue中的元 素按照距离查询点的距离由小到大进行排序，并设优先队列PQueue的初始值为空；

建立保存查询结果的队列ResultList，该队列ResultList的长度为K，队列中元素按距离 查询点的距离升序排列，设队列ResultList初始值为空；

当发出查询请求时，设q表示查询点，o_i表示要查询的兴趣点，其中，i是正整数， 通过步骤二所构建的RRN-Tree索引结构快速定位查询点q所在的路径r₁及通过底层R树 定位查询点所在的路段查找该路段上有一个兴趣点o₁，将o₁及其到q的距离保存 在队列ResultList中，此时，ResultList={<o₁,1>}；

因为路段是单行路，将路段终点及其到查询点的距离入队列PQueue，即： PQueue={<p₂,1>}，查询点与之间没有兴趣点，算法以p₂为起点，通过RRN-Tree中的邻 接链表查找与p₂相邻接的路段继续扩展，将各路段的终点p₁、p₃、 p₄、p₅及其到查询点的距离入队列并按距离升序排列，此时，

PQueue={<p₃,4>,<p₁,5>,<p₅,6>,<p₄,13>}，将队列中距离值最小的元素p₃出队列，该路段上 没有兴趣点对象，则以p₃为起点，继续扩展至p₆，此时，

PQueue={<p₁,5>,<p₅,6>,<p₆,7>,<p₄,13>}；

队列中距离最小值的节点p₁出队列，在路段上，包含对象o₂，将其加入 ResultList队列，ResultList={<o₁,1>,<o₂,3>}；

通过查询RRN-Tree的邻接链表可知，通过节点p₁不再扩展，继续对p₅节点进行处理， 在路段上，包含对象o₃，加入到ResultList队列，同时查询p₅节点的邻接链表，继 续扩展，可得到结果：ResultList={<o₁,1>,<o₂,3>,<o₃,4>}，PQueue={<p₆,7>,<p₄,13>,<p_5-7,17>} 其中，p_5-7表示经过节点5到达节点7；类似的，通过扩展其余节点，得到结果为： ResultList={<o₁,1>,<o₂,3>,<o₃,4>,<o₅,8>}，PQueue={<p_5-7,17>,<p_4-7,20>}；

此时，已经得到4个最近邻对象，距离上界D_max=8；实际上，PQueue中的距离值>D_max， 继续扩展的距离值必定不满足要求，为便于后面的查询更新，以D_max为距离上限，查询点 q为根，计算KNN监测区域，完成KNN查询初始集计算。

具体实施方式三：下面结合图1至图12说明本实施方式，本实施方式为对实施方式 一的进一步说明，本实施方式所述的步骤三中所述CKNN查询更新分为两种情况，当查询 点对象位置不变，而兴趣点对象移动时，利用查询过程生成的KNN监测区可降低查询更新 代价的实现过程为：

当查询点对象不动时，由于查询对象的位置不变，上次查询生成的KNN监测区域也不 变，根据兴趣点对象更新后落在KNN监测区域内对象数量k′值的不同，可分为三种情况 分别处理：

一、当落入KNN监测区域的兴趣点对象k′=k时，只需要通过RRN-Tree查找所有在 KNN监测区域内的路段上的移动对象，将KNN监测区域内内路段上的对象集作为结果；

二、当落入KNN监测区的兴趣点对象k′>k时，需对KNN监测区内的所有移动对象重 新计算与查询对象之间的网络距离，并按照从小到大进行排序，取前k个对象，同时，更 新knn_dist并调整knn监测区，以便下一次更新时继续使用；

三、当落入KNN监测区的兴趣点对象k′<k时，则需要对原KNN监测区域继续扩展， 这里不是从查询对象开始重新扩展，只需从KNN监测区域的标记处开始扩展。

当查询点对象移动时，应用KNN查询初始集计算的查询算法重新计算查询请求的具 体实现过程为：

当处理查询对象和移动对象同时更新时的查询请求，由于在单向行驶的道路网络中， 每个十字路口的转向规则不同，当移动对象运动到十字路口时，路段之间的连通性发生改 变，根据查询对象的运动情况分为两种，当查询对象位置更新后仍然运动在原来的路段上， 并未改变运动方向，可充分利用KNN监测区，提高计算速度；否则，按照KNN查询初始集 计算重新查询。

具体实施例：本实施例从兴趣点对象（POIs）数量、查询请求数、兴趣点对象分布密 度、道路网规模等方面与IMA/GMA算法进行实验对比，实验测试数据集来自TIGER/Line^]下载的加利福尼亚州洛杉矶市（Los Angeles,LA）和旧金山市（San Francisco,SF）的道 路网数据，利用Brinkhoff^[10]设计的基于道路网络的移动对象产生器生成兴趣点对象集。 下载的shp格式数据经过转换工具，生成node节点数据和edge道路边数据，作为移动对 象产生器的输入因子。为便于采用基于路径的建模方式对道路网络建模并建立索引，对两 个道路网络数据集中同名的路段进行合并，形成一条完整路径。实验参数如表1所示。实 验系统采用Java语言编写，运行环境为AMD2.31GHz三核处理器，内存2G，Windows XP SP3操作系统。每次测试只改变其中的一个参数值，其他参数采用默认值。

表1实验参数

Table1experiment parameter

定义7（POI分布密度）：每平方公里面积内道路网络上兴趣点对象的数量，记作：

根据实验过程中产生的POI对象数量和道路网络区域面积，POI分布密度取值范围在 [2,10]之间。

本实施例所述兴趣点对象数量及分布密度对查询时间的影响

图5、图6分别给出了本文算法和IMA/GMA算法在LA、SF道路网环境下POI对象数 量及分布密度变化情况下的CPU响应时间对比情况。从图5中可以看出，CPU响应时间和 POI对象数及分布密度皆成反比例关系，图5中，随着POI对象数量增加，CPU响应时间 明显下降，但是POI数量达到20K以上时，变化趋于平缓。图6中也有类似的变化情况。 本文提出的算法利用索引结构对道路网络进行索引，利用节点的邻接表表示道路之间的连 接关系，采用网络边扩展方式查找最近邻对象，避免了IMA/GMA算法中耗时的最短路径计 算，因此，本文算法比IMA/GMA算法性能提高1.5-2.13倍。

本实施例所述的查询请求数k对查询时间的影响：

图7给出本文算法和IMA/GMA算法在LA、SF道路网络环境下查询请求数k对查询性能 的影响情况。从图中可以看出，随着k值增加，CPU运行时间不断增加，但是本文提出算 法的运行时间明显低于IMA/GMA算法的运行时间。原因在于，本文算法为路径上的交叉点 建立邻接列表，存储交叉点处各路段之间的转向关系，即各路段之间的连接关系，因此， 在计算最短路径时，不符合转向规则的路段被过滤掉，而IMA/GMA算法在计算最短路径时， 采用的是盲目的扩展方式，增加了CPU开销。

基于道路网络的CKNN查询是基于位置服务中的一项重要应用。针对现有CKNN方法处 理道路网面积较大时效率低下和不能处理单向行驶道路网的查询问题，提出RRN-Tree索 引结构，对道路网络及兴趣点对象进行索引，同时在索引结构中为路径上的交叉点建立邻 接链表，存储十字路口处各路段之间的连接关系，从而完成复杂约束条件下道路网络CKNN 查询。实验结果表明，本文提出算法性能优于IMA/GMA算法。方向关系作为查询的约束条 件，在查询中经常被使用，未来工作方向有两个：（1）基于道路网络开展方向关系和最近 邻查询相结合的混合查询算法；（2）基于RNN-Tree索引结构研究基于道路网络的反向最 近邻和概率最近邻[查询问题。

本发明不局限于上述实施方式，还可以是上述各实施方式中所述技术特征的合理组 合。