一种动态路网上基于树分解的kNN查询方法

一种动态路网上基于树分解的knn查询方法
技术领域
1.本发明涉及动态路网上的knn查询领域，尤其涉及一种动态路网上基于树分解的knn查询方法。


背景技术：

2.基于位置的服务(location-based service，简称lbs)可以在任何时间和地点为用户提供正确的位置信息和个性化服务，从而在智能交通系统的应用中起着重大作用。但是，由于现代化交通工具的数量日益增多以及有些城市道路网络设计不规范等不可逆的问题，导致在特定的时间点，比如上下班高峰，容易发生交通不畅甚至阻塞的现象。因此，为了减少该现象的发生，除了增加建设城市道路和桥梁外，在现有的道路网络上，通过合理利用位置信息服务来缓解交通压力，提高出行效率。
3.解决上述问题的关键点是如何合理利用位置服务，要想合理利用好位置服务，那么，就需要完善且高效的路网查询技术。在越来越流行的基于位置的服务中，根据查询点计算k最近邻(knn)是一个典型的应用。knn查询问题在实际生活有着非常广泛的应用，优步软件上的网约车需要查询最快能到达的k个发出租车请求的用户，以方便司机有选择性地接取乘客订单。但是鉴于交通道路上经常且随时可能出现交通堵塞，所以一条路段的通行时间可能随时会发生变化。因此，为了节省网约车司机以及乘客的时间成本。那么，对于网约车司机需要耗时久才能接到乘客的订单就需要被替换。目前，在道路网络中的knn查询问题已经被广泛研究，查询研究工作主要分为基于欧式空间和基于道路网络查询两种。在现有的解决方案中，有些不受现实道路网络的限制，有些查询算法效率有待提高，有些则需要提前预知k值。此外，更重要的是，在实际生活中交通状况是实时变化的，这就使得基于传统静态路网设计的索引和查询算法无法有效满足查询。因此，解决动态路网下knn查询问题有着非常重要的现实意义。


技术实现要素：

4.本发明提供一种动态路网上基于树分解的knn查询方法，以克服上述技术问题。
5.一种动态路网上基于树分解的knn查询方法，包括，
6.步骤一、获取道路网络数据集，根据道路网络数据集构建道路无向加权图，所述道路无向加权图包括顶点集合、边集合以及权重集合，所述顶点为道路网络数据集中的路口，所述边为道路网络数据集中两个路口之间的路段，所述权重为车辆经过路段所需的平均时间，
7.步骤二、根据顶点的度对顶点集合进行升序排序，依次从排序后的顶点集合中选择顶点作为删除顶点，将删除顶点作为主顶点，根据主顶点和主顶点的邻居顶点集构造树节点，并为树节点分配一个删点序号，将树节点与删点序号存储在树节点集合中，根据删点序号对树节点集合进行升序排序，
8.步骤三、获取排序后的树节点集合，对于树节点集合中的每个树节点，将当前树节
点的邻居顶点集中最先作为删除顶点所对应的树节点作为当前树节点的父节点，将当前树节点与父节点进行连接，将连接后的树节点集合作为矮状树分解，
9.步骤四、对矮状树分解的每个树节点进行编号，对于编号后的每个树节点分别构造祖先数组、耗时数组以及子孙表，获取所有树节点的祖先数组、耗时数组以及子孙表集合，
10.步骤五、获取待查询顶点，根据矮状树分解获取待查询顶点的祖先数组，依次计算祖先数组中每一个顶点与待查询顶点之间的最短路网耗时并判断最短路网耗时是否满足第一阈值，若不满足，则获取祖先数组中的下一个顶点，并重新计算顶点与待查询顶点之间的最短路网耗时并判断是否满足更新后的第一阈值，反之，则将祖先数组中的顶点加入至结果集并根据最短路网耗时更新第一阈值，同时获取顶点的子孙表，分别计算结果集中每一个顶点与子孙表中顶点之间的最短路网耗时，并判断顶点与子孙表中顶点之间的最短路网耗时与顶点与待查询顶点之间的最短路网耗时之和是否满足更新后的第一阈值，若最短路网耗时之和满足更新后的第一阈值，则将子孙表中的顶点加入至结果集，并根据最短路网耗时之和更新第一阈值，若最短路网耗时之和不满足更新后的第一阈值，则获取祖先数组中的下一个顶点，并重新计算顶点与待查询顶点之间的最短路网耗时并判断是否满足更新后的第一阈值，
11.步骤六、将结果集中前k个顶点作为待查询顶点的最近邻集合。
12.优选地，所述对于编号后的每个树节点分别构造祖先数组、耗时数组以及子孙表包括使用x(v).anc表示编号后的树节点x(v)的祖先数组，{x(u1),x(u2),
…
,x(uk)}是从x(v)到根节点root路径上的树节点，其中x(u1)是x(v)，x(uk)是root，x(v).anc＝{u1,u2,...,uk}，对于任意1≤i≤k，使用x(v).anci表示x(v).anc中的第i个元素，
13.使用x(v).cost表示树节点x(v)的耗时数组，x(v).anc＝{u1,u2,...,uk}，x(v).cost＝{cost(v,u1),cost(v,u2),
…
,cost(v,uk)}，x(v).cost存储了顶点v到x(v).anc中各顶点的最短路网耗时，对于任意1≤i≤k，使用x(v).costi表示x(v).cost中的第i个元素，x(v).costi＝cost(v,x(v).anci)，
14.树节点x(v)的子孙表用x(v).ccostlist表示，x(v).ccostlist是一个最短路网耗时标签集合，每一个标签是一个二元组，用《u,cost(u,v)》表示，u是x(v)的任意子孙节点对应的主顶点，cost(u,v)为u到v的最短路网耗时。
15.优选地，所述计算祖先数组中每一个顶点与待查询顶点之间的最短路网耗时包括将祖先数组中的顶点表示为v，将待查询顶点表示为u，根据公式(1)计算v与u之间的最短路网耗时，
[0016][0017]
其中，表示v与s之间的权重，x(v).acce表示v的邻居顶点集合，s为邻居顶点集合中的一个顶点，cost(s，u)为s与u之间的最短路网耗时。
[0018]
优选地，所述道路无向加权图的权重改变时，确定权重改变所对应的顶点、附属顶点集合、顶点所对应的树节点以及附属顶点集合所对应的树节点集合，根据最小权重特性和权重传播机制对矮状树分解中树节点对应的边的权重、树节点与附属顶点集合所对应的树节点集合之间的权重进行更新，同时对所有树节点的耗时数组以及子孙表进行更新。
[0019]
优选地，所述树节点的子孙表中设置一个哨兵sen，所述sen用于记录更新前进行knn查询时子孙表所遍历到的最短路网耗时标签位置，当道路无向加权图的权重改变时，通过查看子孙表中sen前受影响的最短路网耗时标签进行增量查询。
[0020]
本发明提供一种动态路网上基于树分解的knn查询方法，设计了矮状树分解中树节点构建和连接方法，改进了传统树分解的生成方法，基于矮状树分解设计了树节点的祖先数组、耗时数组以及子孙表集合，并将其作为底层索引。同时，基于最短路网耗时进行高效查询，并根据最短路网耗时与第一阈值的关系在查询过程中进行了剪枝，减少了大量不必要的计算，从而提高了knn查询的时间效率。然后，提出了路网动态更新时索引的维护方法，并设计了增量查询算法以满足查询效率。解决了目前已有knn查询方法中有些不受路网限制，有些不能灵活适应k值变化，有些只适用于静态路网的问题，更重要的是，本发明提出的查询算法在保证knn查询的正确性的前提下，极大提高了查询时间和效率。
附图说明
[0021]
为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实施例或现有技术描述中所需要使用的附图作一简单地介绍，显而易见地，下面描述中的附图是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动性的前提下，还可以根据这些附图获得其他的附图。
[0022]
图1是本发明方法流程图；
[0023]
图2是本发明在计算knn查询时所采用的道路网络数据示例图；
[0024]
图3是本发明用改进的树分解生成策略生成的矮状树分解示例图；
[0025]
图4是本发明基于矮状树分解构造的索引结构；
[0026]
图5是本发明索引结构ddt-index中各节点的子孙表；
[0027]
图6是本发明knn查询算法的流程图；
[0028]
图7是本发明以查询顶点v7的5nn(q＝v7,k＝5)为例的示意图；
[0029]
图8是本发明ss-graph逻辑结构图以及路网更新时边权值的维护过程图；
[0030]
图9是本发明路网g中边(v8,v9)权值增加对应的ddt-index以及各节点x(vi)的子孙表；
[0031]
图10是本发明路网g中边(v7,v5)的权值减少对应的ddt-index以及各节点x(vi)的子孙表；
[0032]
图11是本发明增量查询v7的5nn的示例图。
具体实施方式
[0033]
为使本发明实施例的目的、技术方案和优点更加清楚，下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有作出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。
[0034]
图1为本发明方法流程图，如图1所示，本实施例的方法可以包括：
[0035]
步骤一、获取道路网络数据集，根据道路网络数据集构建道路无向加权图，所述道路无向加权图包括顶点集合、边集合以及权重集合，所述顶点为道路网络数据集中的路口，
所述边为道路网络数据集中两个路口之间的路段，所述权重为车辆经过路段所需的平均时间，
[0036]
步骤二、根据顶点的度对顶点集合进行升序排序，依次从排序后的顶点集合中选择顶点作为删除顶点，将删除顶点作为主顶点，根据主顶点和主顶点的邻居顶点集构造树节点，并为树节点分配一个删点序号，将树节点与删点序号存储在树节点集合中，根据删点序号对树节点集合进行升序排序，
[0037]
步骤三、获取排序后的树节点集合，对于树节点集合中的每个树节点，将当前树节点的邻居顶点集中最先作为删除顶点所对应的树节点作为当前树节点的父节点，将当前树节点与父节点进行连接，将连接后的树节点集合作为矮状树分解，
[0038]
步骤四、对矮状树分解的每个树节点进行编号，对于编号后的每个树节点分别构造祖先数组、耗时数组以及子孙表，获取所有树节点的祖先数组、耗时数组以及子孙表集合，
[0039]
步骤五、获取待查询顶点，根据矮状树分解获取待查询顶点的祖先数组，依次计算祖先数组中每一个顶点与待查询顶点之间的最短路网耗时并判断最短路网耗时是否满足第一阈值，若不满足，则获取祖先数组中的下一个顶点，并重新计算顶点与待查询顶点之间的最短路网耗时并判断是否满足更新后的第一阈值，反之，则将祖先数组中的顶点加入至结果集并根据最短路网耗时更新第一阈值，同时获取顶点的子孙表，分别计算结果集中每一个顶点与子孙表中顶点之间的最短路网耗时，并判断顶点与子孙表中顶点之间的最短路网耗时与顶点与待查询顶点之间的最短路网耗时之和是否满足更新后的第一阈值，若最短路网耗时之和满足更新后的第一阈值，则将子孙表中的顶点加入至结果集，并根据最短路网耗时之和更新第一阈值，若最短路网耗时之和不满足更新后的第一阈值，则获取祖先数组中的下一个顶点，并重新计算顶点与待查询顶点之间的最短路网耗时并判断是否满足更新后的第一阈值，
[0040]
步骤六、将结果集中前k个顶点作为待查询顶点的最近邻集合。
[0041]
基于上述方案，设计了矮状树分解中树节点构建和连接方法，改进了传统树分解的生成方法，基于矮状树分解设计了树节点的祖先数组、耗时数组以及子孙表集合，并将其作为底层索引。同时，基于最短路网耗时进行高效查询，并根据最短路网耗时与第一阈值的关系在查询过程中进行了剪枝，减少了大量不必要的计算，从而提高了knn查询的时间效率。然后，提出了路网动态更新时索引的维护方法，并设计了增量查询算法以满足查询效率。在保证knn查询的正确性的前提下，极大提高了查询时间效率。
[0042]
步骤一、获取道路网络数据集，根据道路网络数据集构建道路无向加权图，所述道路无向加权图包括顶点集合、边集合以及权重集合，所述顶点为道路网络数据集中的路口，所述边为道路网络数据集中两个路口之间的路段，所述权重为车辆经过路段所需的平均时间，具体地，将道路网络(以下简称路网)建模成一个无向加权图g(v,e)，用v和e分别表示的是路网中顶点和边的集合。
[0043]
g中的每个顶点v∈v表示道路的交叉口或者道路终点(假定用户发出的租车请求都位于道路口)，用边e(u,v)∈e(u≠v)表示路口u和路口v之间的路段，并且每条边对应有一个权重表示经过此路段平均需要花费的时间。
[0044]
对于每个顶点v∈v，用nbr(v)＝{u|(u,v)∈e}表示顶点v的所有邻居顶点集合，并
且用deg(v)＝|nbr(v)|表示顶点v的度，即邻居顶点的数量。
[0045]
步骤二、根据顶点的度对顶点集合进行升序排序，所述顶点的度为顶点的邻居顶点的数量，顶点v的度表示为deg(v)＝|nbr(v)|，依次从排序后的顶点集合中选择顶点作为删除顶点，将删除顶点作为主顶点，根据主顶点和主顶点的邻居顶点集构造树节点，并为树节点分配一个删点序号，将树节点与删点序号存储在树节点集合中，根据删点序号对树节点集合进行升序排序，
[0046]
步骤三、获取排序后的树节点集合，对于树节点集合中的每个树节点，将当前树节点的邻居顶点集中最先作为删除顶点所对应的树节点作为当前树节点的父节点，将当前树节点与父节点进行连接，将连接后的树节点集合作为矮状树分解，
[0047]
具体地，步骤二和步骤三为生成矮状树分解ddt(dwarf tree decomposition)的过程，
[0048]
步骤2.1：顶点删除，利用删点策略，将路网g中顶点依次删除构造树节点，并为每个树节点分配一个删点序号r，删除g中所有顶点后，形成树节点集合λ。
[0049]
树节点用x(v)表示，x(v)由v以及v的邻居顶点组成，本实施例中将v称为x(v)的主顶点，并用x(v).acce表示v的邻居顶点集合，称之为x(v)的附属顶点集。
[0050]
矮状树删点策略：为了保证树分解树宽尽可能小，按照g中每个顶点的度的升序顺序选择顶点。对于度相同的顶点，选择前邻居数更小的顶点作为删除顶点。
[0051]
前邻居指的是对于要删除的顶点v，假设在v之前删除的顶点集合为vpre，对于任意顶点v’∈vpre，若v∈x(v’).acce，则v’是v的前邻居。
[0052]
例如图3中，假设下一个要删除的顶点是v7，在v7之前删除的顶点集合x(v7).vpre＝{v8,v
10
,v9,v6}，其中，v7∈x(v9).acce，v7∈x(v6).acce，则可以得出exnbr(v7)＝2。
[0053]
步骤2.2：树分解构造，将路网中所有顶点删除后形成的树节点集合λ，根据删点序号，对于λ中每个树节点x(v)，将其附属顶点集中最先被删除的顶点对应的树节点作为x(v)的父节点进行连接，最终构成分解ddt。
[0054]
步骤四、对矮状树分解的每个树节点进行编号，对树节点进行编号具体包括，对ddt中的每个树节点x(v)进行编号，用x(v).no表示。若子节点x(v)i是其父节点x(v)j的第m个孩子，那么x(v)i.no＝x(v)j.no+
‘
m’。规定根节点的编号为1。当m超过9时，可以用字母字符串继续编号。通过对树节点进行编号，只需要找出任意两个树节点编号的最长公共前缀即可快速确定该两个树节点之间的关系以及最小公共祖先。比如，当树节点x(v)和x(u)对应的编号的最长公共前缀长度等于两树节点编号长度之一，那么x(v)和x(u)是祖先后代的关系，否则，x(v)和x(u)的最小公共祖先对应的树节点编号为此时的最长公共前缀。通过确定任意两个主顶点的祖先后代关系以及最小公共祖先，可以快速求该两点的最短耗时。
[0055]
对于编号后的每个树节点分别构造祖先数组、耗时数组以及子孙表，所述对于编号后的每个树节点分别构造祖先数组、耗时数组以及子孙表包括使用x(v).anc表示编号后的树节点x(v)的祖先数组，{x(u1),x(u2),
…
,x(uk)}是从x(v)到根节点root路径上的树节点，其中x(u1)是x(v)，x(uk)是root，x(v).anc＝{u1,u2,...,uk}，对于任意1≤i≤k，使用x(v).anci表示x(v).anc中的第i个元素。
[0056]
使用x(v).cost表示树节点x(v)的耗时数组，x(v).anc＝{u1,u2,...,uk}，x(v).cost＝{cost(v,u1),cost(v,u2),
…
,cost(v,uk)}，x(v).cost存储了顶点v到x(v).anc中
各顶点的最短路网耗时，对于任意1≤i≤k，使用x(v).costi表示x(v).cost中的第i个元素，x(v).costi＝cost(v,x(v).anci)，
[0057]
树节点x(v)的子孙表用x(v).ccostlist表示，x(v).ccostlist是一个最短路网耗时标签集合，每一个标签是一个二元组，用《u,cost(u,v)》表示，u是x(v)的任意子孙节点对应的主顶点，cost(u,v)为u到v的最短路网耗时。
[0058]
获取所有树节点的祖先数组、耗时数组以及子孙表集合，
[0059]
步骤五、获取待查询顶点，根据矮状树分解获取待查询顶点的祖先数组，依次计算祖先数组中每一个顶点与待查询顶点之间的最短路网耗时并判断最短路网耗时是否满足第一阈值，若不满足，则获取祖先数组中的下一个顶点，并重新计算顶点与待查询顶点之间的最短路网耗时并判断是否满足更新后的第一阈值，反之，则将祖先数组中的顶点加入至结果集并根据最短路网耗时更新第一阈值，同时获取顶点的子孙表，分别计算结果集中每一个顶点与子孙表中顶点之间的最短路网耗时，并判断顶点与子孙表中顶点之间的最短路网耗时与顶点与待查询顶点之间的最短路网耗时之和是否满足更新后的第一阈值，若最短路网耗时之和满足更新后的第一阈值，则将子孙表中的顶点加入至结果集，并根据最短路网耗时之和更新第一阈值，若最短路网耗时之和不满足更新后的第一阈值，则获取祖先数组中的下一个顶点，并重新计算顶点与待查询顶点之间的最短路网耗时并判断是否满足更新后的第一阈值，
[0060]
所述计算祖先数组中每一个顶点与待查询顶点之间的最短路网耗时包括将祖先数组中的顶点表示为v，将待查询顶点表示为u，根据公式(1)计算v与u之间的最短路网耗时，
[0061][0062]
其中，表示v与s之间的权重，x(v).acce表示v的邻居顶点集合，s为邻居顶点集合中的一个顶点，cost(s，u)为s与u之间的最短路网耗时。
[0063]
步骤六、将结果集中前k个顶点作为待查询顶点的最近邻集合。
[0064]
所述步骤五和六可以视为进行knn查询的过程，具体为，
[0065]
步骤4.1：获取查询点q的处理顶点表，即x(q).anc。
[0066]
步骤4.2：依次扫描x(q).anc中的顶点，对扫描到的第i(1≤i≤|x(q).anc|)个顶点s，计算cost(q,s)，cost(q,s)＝x(q).costi，若cost(q,s)≤threshold，则把s加入结果集r并更新threshold，否则继续扫描第i+1个祖先节点。
[0067]
步骤4.3：对于加入结果集r的顶点s，依次扫描x(s).ccostlist中标签对应的顶点vi，并计算curcost(q,vi,s)，curcost(q,vi,s)＝cost(q,s)+cost(vi,s)，若curcost(q,vi,s)≤threshold，则把vi加入结果集r并更新threshold，否则停止扫描当前x(s).ccostlist。重复步骤4.2和步骤4.3，直至扫描完x(q).anc中的所有顶点。
[0068]
为了减少计算代价，在步骤4.2和4.3中设计以下剪枝策略：
[0069]
策略1：当查询点q到祖先节点x(s)对应的主顶点s的最短路网耗时大于或者等于阈值时，根据定理1，则不需要再继续扫描x(s).ccostlist中的标签。
[0070]
策略2：当查询点q经过祖先节点x(s)到达顶点v的当前最短路网耗时大于阈值时，根据定理2，v之后的耗时标签不需要再继续扫描计算。
[0071]
策略3：给定查询点q，根据定理3，对于已经扫描计算过的顶点v(v∈x(q)
.ccostlist)，在x(q)的其他祖先节点的子孙表中不需要重复计算。
[0072]
策略4：给定查询点q，对于已经扫描计算过的顶点v(v∈x(q).anc)，若v出现在其他祖先节点x(s)的子孙表中，根据定理4，不需要计算x(s).ccostlis中顶点v对应的耗时标签。
[0073]
其中，定理1：给定查询点q和任意x(q)的祖先节点顶点x(s)，若cost(q,s)≥threshold，那么，对于任意顶点v∈x(s).ccostlist，有curcost(q,v,s)＞threshold。
[0074]
证明：给定查询点q和任意x(q)的祖先节点顶点x(s)，对于任意顶点v∈x(s).ccostlist，curcost(q,v,s)＝cost(q,s)+cost(v,s)，由于cost(q,s)≥threshold且cost(v,s)》0，因此，curcost(q,v,s)》threshold，所以v一定不可能是q的knn。
[0075]
定理2：给定查询点q和任意x(q)的祖先节点顶点x(s)，若cost(q,s)＜threshold且curcost(q,v,s)＞threshold(v∈x(s).ccostlist)，对于任意排序在v之后的顶点p∈x(q).ccostlist，有curcost(q,p,s)＞threshold。
[0076]
证明：对于任意排序在v之后的顶点p∈x(q).ccostlist，容易得出cost(p,s)》cost(v,s)，由于curcost(q,v,s)＝cost(v,s)+cost(q,s)》threshold，则有curcost(q,p,s)＝cost(q,s)+cost(p,s)》curcost(q,v,s)》threshold，因此，p一定不可能是q的knn。
[0077]
定理3：给定查询点q，对于任意顶点v∈x(q).ccostlist∪q，有curcost(q,v,q)＝cost(q,v)。
[0078]
证明：对于任意顶点v∈x(q).ccostlist∪q，curcost(q,v,q)＝cost(q,q)+cost(v,q)，由于cost(q,q)＝0，所以curcost(q,v,q)＝cost(q,v)。
[0079]
定理4：给定查询点q和任意x(q)的祖先节点x(s)，对于任意v∈x(q).anc且v∈x(s).ccostlist，有cost(q,v)≤curcost(q,v,s)。
[0080]
证明：根据公式(1)，若s∈x(q).acce，则cost(q,v)≤curcost(q,v,s)，若则cost(q,v)《curcost(q,v,s)，综上cost(q,v)≤curcost(q,v,s)。
[0081]
所述道路无向加权图的权重改变时，确定权重改变所对应的顶点、附属顶点集合、顶点所对应的树节点以及附属顶点集合所对应的树节点集合，根据最小权重特性和权重传播机制对矮状树分解中树节点对应的边的权重、树节点与附属顶点集合所对应的树节点集合之间的权重进行更新，同时对所有树节点的耗时数组以及子孙表进行更新。
[0082]
其中，最小权重特性为：给定矮状树分解ddt对应的ss-graph，本发明将连接箭头前端的顶点称作内邻居，将连接箭头末端的顶点称作外邻居。设v
r1
,v
r2
,...,v
rn
是vs的内邻居，v
s11
,v
s12
,v
s21
,v
s22
,...,v
sn1
,v
sn2
是v
r1
,v
r2
,...,v
rn
的内邻居，给定任意一条快捷边s，如果果则可以说vs满足最小权重性质。对于ss-graph中的每个矩形顶点都满足最小权重性质。
[0083]
快捷边权重传播机制为：根据最小权重特性，在ss-graph中，对于快捷边s对应的矩形顶点vs，当其中之一改变时，可能会使得vs违反最小权重特性。当改变时，可能会进一步影响上层矩形顶点违反最小权重特性。因此，当一条快捷边s的权值改变时，先判断vs是否违反最小权重特性。如果违反，则调整然后将vs的外邻居的外邻居作为进一步调整的候选顶点。如果不违反，则不需要进行其他处理。按照这种机制，迭代地调整直到所有矩形顶点都满足最小权重特
性。
[0084]
具体地，对于图g中边权重增加和减少的情况，本实施例根据最小权重特性和权重传播机制，对ss-graph中的矩形顶点对应的边的权值进行更新，同时更新树节点中主顶点到附属顶点的权值。其中，ss-graph与ddt是同一种物理结构，其对应的逻辑视图可以看成是一个包含两种顶点的有向图。图中矩形顶点一一对应矮状树分解ddt的树节点中主顶点到各个附属顶点对应的边。圆形顶点表示的是一种影响关系，即对于一个顶点v的两条邻边(v,u)和(v,w)权值改变可能会影响边(u,w)的权值发生改变。更新完树节点中主顶点到附属顶点的权值后，根据公式更新每个树节点的cost数组，
[0085]
当路网更新时，增量查询可以结合上一次查询结果，更快速的返回knn查询结果。具体为，分别在树节点的子孙表中设置一个哨兵sen，所述sen用于记录更新前进行knn查询时子孙表所遍历到的最短路网耗时标签位置，当道路无向加权图的权重改变时，通过查看子孙表中sen前受影响的最短路网耗时标签进行增量查询。增量查询时顶点的扫描策略具体为，：
[0086]
1)如果祖先节点x(v)到查询点的最短路网耗时不变，仅是祖先节点的子孙表中某些耗时标签受影响改变，并且最前受影响标签的索引下标大于sen，则可以继续向上扫描祖先节点；如果第一个受影响的耗时标签索引下标小于或者等于sen，那么需要从第一个受影响的标签开始依次扫描顶点并计算其到查询点的当前最短路网耗时，第一个受影响的耗时标签之前的标签则不需要再进行计算。
[0087]
2)如果祖先节点x(v)到查询点的最短路网耗时改变，那么就需要重新依次扫描x(v)的子孙表并计算其到查询点的当前最短路网耗时，后续的祖先顶点也需重新扫描其子孙表。
[0088]
图2为本实施例在计算knn查询时所采用的道路网络数据示例图。其中的每个顶点v表示道路的交叉口或者道路终点，假定用户发出的租车请求都位于道路口，每条边e(u,v)表示路口u和路口v之间的路段，每条边对应有一个权重表示经过此路段平均需要花费的时间，我们称之为路网耗时。为了方便，不考虑路网中边的方向。
[0089]
图3为将图2所示路网图利用改进的树分解生成策略生成的矮状树分解示例图，其中左图为将图2中顶点按照删点策略依次删除形成的树节点集合，其中每个树节点有一个删点序号，每个树节点由主顶点和主顶点的邻居顶点组成，并且还包含了主顶点到各邻居顶点的路网耗时。
[0090]
例如，删除顶点v8时，先将与顶点v8相邻的顶点v9和v5加入集合x(v8)中，x(v8)＝{v9,v5}，并保留顶点v8到顶点v9和v5的权值，然后删除与顶点v8相连的边，并在顶点v9和v5之间添加一条边，其权值为删除顶点v8后成了对应的树节点x(v8)＝{v8,v9,v5}，x(v8).acce＝{v9,v5}。
[0091]
其中右图即为生成的矮状树分解，在构建阶段中，将树节点集合λ中的每个树节点x(v)，根据删点序r，将其附属顶点中最先被删除的顶点对应的树节点作为x(v)的父节点进行连接，最终构成矮状树分解ddt。例如顶点v9对应的树节点x(v9)的删点序号是x(v8)的附属顶点集中最小的，所以将树节点x(v9)作为树节点x(v8)的父节点进行连接。
[0092]
图4为图2基于矮状树分解构造的索引结构，对于每个节点除了x(v)之外还由三部分组成，包括节点编号x(v).no，祖先数组x(v).anc，耗时数组x(v).cost；通过对树节点进行编号，只需要找出任意两个树节点编号的最长公共前缀即可快速确定该两个树节点之间的关系以及最小公共祖先。
[0093]
比如，当树节点x(v)和x(u)对应的编号的最长公共前缀长度等于两树节点编号长度之一，那么x(v)和x(u)是祖先后代的关系，否则，x(v)和x(u)的最小公共祖先对应的树节点编号为此时的最长公共前缀。通过确定任意两个主顶点的祖先后代关系以及最小公共祖先，可以快速求出该两点的最短耗时。
[0094]
在图4中，根节点x(v0)的编号为1，子节点x(v9)是其父节点x(v5)的第一个孩子节点，由于x(v5).no＝11，则x(v9).no＝111；x(v2)是x(v5)的第二个孩子节点，则x(v2).no＝112。每个树节点x(v)的祖先数组存储了从x(v)到根节点root路径上的树节点对应的主顶点，祖先数组中的元素与耗时数组中的元素一一对应，例如，树节点x(v4)的祖先数组为x(v4).anc＝{v4,v2,v5,v0}，其中，x(v).anc2＝v2。树节点x(v)的耗时数组存储了主顶点v到x(v).anc中各顶点的最短路网耗时。
[0095]
树节点x(v4)的耗时数组为x(v4).cost＝{0,2,3,2}，表示到各祖先节点对应的主顶点v4,v2,v5,v0的最短路网耗时分别为0,2,3,2。通过数组下标可以获取查询点到各祖先节点的主顶点对应的最短路网耗时，例如x(v4).cost2＝2，表示顶点v4到祖先节点x(v2)对应的主顶点v2的最短路网耗时为2。
[0096]
图5为索引结构ddt-index中各节点的子孙表，例如，表中x(v9).ccostlist＝{(v7,1),(v6,1),(v8,2)}，表示树节点x(v9)的子孙节点对应的主顶点有v7,v6,v8，顶点v9到其各子孙节点对应的主顶点的最短路网耗时升序序列分别为1,1,2。
[0097]
图6为本发明中knn查询算法的流程图，
[0098]
给定查询点q和整数k后，
[0099]
第一步，获取查询点q的处理顶点表，即x(q).anc。
[0100]
第二步，依次扫描x(q).anc中的顶点，对扫描到的第i(1≤i≤|x(q).anc|)个顶点s，计算cost(q,s)，cost(q,s)＝x(q).costi，若cost(q,s)≤threshold，则把s加入结果集r并更新threshold，否则继续扫描第i+1个祖先节点。
[0101]
第三步，对于加入结果集r的顶点s，依次扫描x(s).ccostlist中标签对应的顶点vi，并计算curcost(q,vi,s)，curcost(q,vi,s)＝cost(q,s)+cost(vi,s)，若curcost(q,vi,s)≤threshold，则把vi加入结果集r并更新threshold，否则停止扫描当前x(s).ccostlist。
[0102]
重复第二步和第三步，直至扫描完x(q).anc中的所有顶点。
[0103]
图7为以查询顶点v7的5nn(q＝v7,k＝5)为例，首先获取x(v7)的祖先数组中的顶点作为处理顶点，x(v7).anc＝{v7,v9,v5,v0,}，对于x(v7)，由于v7为查询点本身，不需进行处理，然后扩展其子孙表得到x(v7).ccostlist＝{《v6,2》}，计算curcost(v7,v6,v6)＝cost(v7,v6)＝2小于阈值，所以将v6加入结果集r，此时r＝{v6}。
[0104]
对于顶点v9，由于cost(v7,v9)＝1小于阈值，将v9加入结果集r。此时，r＝{v9,v6}且|r|＝2《k，所以继续扫描其子孙表。x(v9).ccistlist＝{《v7,1》,《v6,1》,《v8,2》}，v7是查询点本身不需处理，x(v6)是x(v7)的子孙节点，根据策略3，所以v6也不需处理。对于顶点v8，由
于curcost(v7,v8,v9)＝cost(v7,v9)+cost(v8,v9)＝3小于阈值，所以将v8加入结果集。此时，结果集r＝{v9,v6,v8}。
[0105]
对于顶点v5，cost(v7,v5)＝4仍小于阈值，将v5加入结果集，此时，r＝{v9,v6,v8,v5}且|r|＝4《k，所以继续扫描其子孙表。
[0106]
x(v5).ccistlist＝{《v8,2》,《v3,2》,《v4,3》,《v2,4》,《v9,4》,
[0107]
《v7,4》,《v1,4》,《v6,5》,《v
10
,6》}，对于顶点v8，由于curcost(v7,v8,v5)＝6《curcost(v7,v8,v9)＝3，所以不做处理。对于顶点v3，由于curcost(v7,v3,v5)＝cost(v7,v5)+cost(v3,v5)＝6小于阈值，所以将v3加入结果集。
[0108]
此时，r＝{v9,v6,v8,v5,v3}且|r|＝5＝k，所以阈值更新为6，当扫描到顶点v4时，由于curcost(v7,v4,v5)＝7》threshold＝6，根据策略2，可以停止扫描x(v5).ccistlist。继续扫描查询点v7的祖先数组，当扫描顶点v0时，由于cost(v7,v0)＝4《threshold＝6，所以将加入结果集r并更新阈值threshold＝4。此时，r＝{v9,v6,v8,v5,v0}。根据策略1，则不需要再扫描x(v0).ccostlist。至此，x(v7)的所有祖先节点扫描完毕。由于k＝5，所以，取结果集r中前5个顶点对象，最终得到v7的5nn为{v9,v6,v8,v5,v0}。
[0109]
图8为ss-graph逻辑结构图以及路网更新时边权值的维护过程，本发明利用该逻辑结构对路网动态更新时索引结构进行维护。ss-graph与ddt是同一种物理结构，其对应的逻辑视图可以看成是一个包含两种顶点的有向图，如图8所示。图中矩形顶点一一对应矮状树分解ddt的树节点中主顶点到各个附属顶点对应的边。圆形顶点表示的是一种影响关系，即对于一个顶点v的两条邻边(v,u)和(v,w)权值改变可能会影响边(u,w)的权值。矩形顶点的上部分表示边，右下部分表示该边两端顶点的最短路网耗时，左下部分是一个权重计数器，表示得到该最短路网耗时的方案数，用cnt表示。为了方便描述，本发明将矩形顶点对应的边称作快捷边，用vs表示，圆形顶点用vr表示。
[0110]
以图8中(v7,v0)对应的矩形顶点为例，顶点v7到v0的最短路网耗时为4，权重计数器为2表示v7既可以直接到v0也可以经过v6到达v0，并且这两种方案的路网耗时是相等的。
[0111]
在维护过程中，使用一个队列q来存储受影响的矩形顶点。
[0112]
对于边权值减小的情况，例如，边(v7,v5)的权值从4减为2。根据最小权重特性，先检查矩形顶点v(v7,v5)的权值是否受影响，通过计)的权值是否受影响，通过计说明v(v7,v5)的权值受影响，所以修改并将v(v7,v5)加入队列q，此时q＝{v(v7,v5)}。
[0113]
然后v(v7,v5)出队，由于矩形顶点v(v7,v5)权值的改变，通过ss-graph查看矩形顶点v(v7,v5)的外邻居的外邻居有矩形顶点v(v9,v5)和矩形顶点v(v5,v0)可能成为下一步受影响的顶点。
[0114]
检查矩形顶点v(v9,v5)，
[0115][0115]
说明该顶点权值受到影响，修改并将加入队列q。
[0116]
对于矩形顶点v((v5,v0))，
[0117]
说明矩形顶点(v5,v0)权值不受矩形顶点v(v7,v5)权值改变的影响。此时，队列q＝{v(v9,v5)}。
[0118]
同理，由于v(v9,v5)权值的改变，只可能会影响v(v5,v0)，利用最小权重特性经过计算发现v(v5,v0)不受影响。此时，队列为空，即可停止检查。
[0119]
对于边权值增加的情况，例如，边(v6,v9)的权值从1增加为2，由于边(v6,v9)的权值改变之前，因此v(v6,v9)的权重计数器减1，此时，v(v6,v9).cnt＝1-1＝0，说明边(v6,v9)的权值改变一定会影响v(v6,v9)的权值。因此，将v(v6,v9)加入队列q，此时，q＝{v(v6,v9)}。
[0120]
然后，v(v6,v9)出队，首先计算v(v6,v9)的权值改变可能会影响的矩形顶点，v(v6,v9)的外邻居的外邻居有v(v9,v7)和v(v9,v0)。
[0121]
对于v(v9,v7)，由于说明v(v6,v9)的权值改变不会影响v(v9,v7)的权值。
[0122]
对于v(v9,v0)，由于说明v(v6,v9)的权值改变可能会影响v(v9,v7)的权值，将v(v9,v0)的权重计数器减1，此时v(v9,v0).cnt＝1-1＝0，说明v(v6,v9)的权值改变一定会影响v(v9,v0)的权值，所以将v(v9,v0)加入队列q。检查完v(v6,v9)的权值改变可能会影响的矩形顶点后，最后利用最小权重特性计算同时将x(v6)中到附属顶点v9的权值修改为2。此时q＝{v(v9,v0)}。v(v9,v0)出队后，同理首先查看v(v9,v0)权值改变可能会影响的矩形顶点。对于v(v9,v0)的外邻居的外邻居v(v5,v0)，由于因此，的权值一定不会受v(v6,v9)权值改变的影响，检查完v(v9,v0)权值改变可能会影响的矩形顶点。
[0123]
然后，利用最小权重特性计算然后，利用最小权重特性计算同时将x(v9)中到附属顶点v0的权值修改为4。此时，队列q为空，即可停止检查。
[0124]
图9和图10分别为路网g中边(v8,v9)权值从2增加为4，边(v7,v5)的权值从4减为2后，对应的ddt-index以及各节点x(vi)的子孙表。
[0125]
图11为增量查询v7的5nn的示例。为每个节点x(v)设置了一个pos数组，用来表示v到x(v).anc的路网耗时是否发生变化，默认值为false。增量查询算法初始的扫描节点仍然是从查询点对应的树节点开始。由于x(v7)到其自身的路网耗时不会发生变化并且eff＝-1，因此，可以直接将上次扫描节点x(v7)的计算结果直接加入结果集r并更新阈值。当扫描到节点x(v9)时，x(v7).pos2＝false，说明x(v7)到祖先节点x(v9)的最短路网时间并没有发生变化，但是x(v9).eff＝3，表明x(v9)的子孙表有变化并且第一个受影响的标签的节点是v8，此外，x(v9).sen＝3，所以根据本文的扫描策略，可以将v8之前的标签对应的节点加入结果集并更新阈值，并从v8开始继续扫描子孙表。当扫描到祖先节点x(v5)时，x(v7).pos2＝true，说明x(v7)到祖先节点x(v5)的最短路网时间发生了改变，因此，需要从头开始扫描x(v5)的子孙表。同理，扫描完x(v0)之后最终得出结果集r＝{v9,v6,v5,v3,v0}。
[0126]
整体的有益效果：
[0127]
本发明提供一种动态路网上基于树分解的knn查询方法，设计了矮状树分解中树节点构建和连接方法，改进了传统树分解的生成方法，基于矮状树分解设计了树节点的祖先数组、耗时数组以及子孙表集合，并将其作为底层索引。同时，基于最短路网耗时进行高效查询，并根据最短路网耗时与第一阈值的关系在查询过程中进行了剪枝，减少了大量不必要的计算，从而提高了knn查询的时间效率。然后，提出了路网动态更新时索引的维护方法，并设计了增量查询算法以满足查询效率。解决了目前已有knn查询方法中有些不受路网限制，有些不能灵活适应k值变化，有些只适用于静态路网的问题，更重要的是，本发明提出的查询算法在保证knn查询的正确性的前提下，极大提高了查询时间和效率。
[0128]
最后应说明的是：以上各实施例仅用以说明本发明的技术方案，而非对其限制；尽管参照前述各实施例对本发明进行了详细的说明，本领域的普通技术人员应当理解：其依然可以对前述各实施例所记载的技术方案进行修改，或者对其中部分或者全部技术特征进行等同替换；而这些修改或者替换，并不使相应技术方案的本质脱离本发明各实施例技术方案的范围。

技术特征：
1.一种动态路网上基于树分解的knn查询方法，其特征在于，包括，步骤一、获取道路网络数据集，根据道路网络数据集构建道路无向加权图，所述道路无向加权图包括顶点集合、边集合以及权重集合，所述顶点为道路网络数据集中的路口，所述边为道路网络数据集中两个路口之间的路段，所述权重为车辆经过路段所需的平均时间，步骤二、根据顶点的度对顶点集合进行升序排序，依次从排序后的顶点集合中选择顶点作为删除顶点，将删除顶点作为主顶点，根据主顶点和主顶点的邻居顶点集构造树节点，并为树节点分配一个删点序号，将树节点与删点序号存储在树节点集合中，根据删点序号对树节点集合进行升序排序，步骤三、获取排序后的树节点集合，对于树节点集合中的每个树节点，将当前树节点的邻居顶点集中最先作为删除顶点所对应的树节点作为当前树节点的父节点，将当前树节点与父节点进行连接，将连接后的树节点集合作为矮状树分解，步骤四、对矮状树分解的每个树节点进行编号，对于编号后的每个树节点分别构造祖先数组、耗时数组以及子孙表，获取所有树节点的祖先数组、耗时数组以及子孙表集合，步骤五、获取待查询顶点，根据矮状树分解获取待查询顶点的祖先数组，依次计算祖先数组中每一个顶点与待查询顶点之间的最短路网耗时并判断最短路网耗时是否满足第一阈值，若不满足，则获取祖先数组中的下一个顶点，并重新计算顶点与待查询顶点之间的最短路网耗时并判断是否满足更新后的第一阈值，反之，则将祖先数组中的顶点加入至结果集并根据最短路网耗时更新第一阈值，同时获取顶点的子孙表，分别计算结果集中每一个顶点与子孙表中顶点之间的最短路网耗时，并判断顶点与子孙表中顶点之间的最短路网耗时与顶点与待查询顶点之间的最短路网耗时之和是否满足更新后的第一阈值，若最短路网耗时之和满足更新后的第一阈值，则将子孙表中的顶点加入至结果集，并根据最短路网耗时之和更新第一阈值，若最短路网耗时之和不满足更新后的第一阈值，则获取祖先数组中的下一个顶点，并重新计算顶点与待查询顶点之间的最短路网耗时并判断是否满足更新后的第一阈值，步骤六、将结果集中前k个顶点作为待查询顶点的最近邻集合。2.根据权利要求1所述的一种动态路网上基于树分解的knn查询方法，其特征在于，所述对于编号后的每个树节点分别构造祖先数组、耗时数组以及子孙表包括使用x(v).anc表示编号后的树节点x(v)的祖先数组，{x(u1),x(u2),
…
,x(u
k
)}是从x(v)到根节点root路径上的树节点，其中x(u1)是x(v)，x(u
k
)是root，x(v).anc＝{u1,u2,...,u
k
}，对于任意1≤i≤k，使用x(v).anc
i
表示x(v).anc中的第i个元素，使用x(v).cost表示树节点x(v)的耗时数组，x(v).anc＝{u1,u2,...,u
k
}，x(v).cost＝{cost(v,u1),cost(v,u2),
…
,cost(v,u
k
)}，x(v).cost存储了顶点v到x(v).anc中各顶点的最短路网耗时，对于任意1≤i≤k，使用x(v).cost
i
表示x(v).cost中的第i个元素，x(v).cost
i
＝cost(v,x(v).anc
i
)，树节点x(v)的子孙表用x(v).ccostlist表示，x(v).ccostlist是一个最短路网耗时标签集合，每一个标签是一个二元组，用<u,cost(u,v)>表示，u是x(v)的任意子孙节点对应的主顶点，cost(u,v)为u到v的最短路网耗时。3.根据权利要求1所述的一种动态路网上基于树分解的knn查询方法，其特征在于，所述计算祖先数组中每一个顶点与待查询顶点之间的最短路网耗时包括将祖先数组中的顶
点表示为v，将待查询顶点表示为u，根据公式(1)计算v与u之间的最短路网耗时，其中，表示v与s之间的权重，x(v).acce表示v的邻居顶点集合，s为邻居顶点集合中的一个顶点，cost(s，u)为s与u之间的最短路网耗时。4.根据权利要求1所述的一种动态路网上基于树分解的knn查询方法，其特征在于，所述道路无向加权图的权重改变时，确定权重改变所对应的顶点、附属顶点集合、顶点所对应的树节点以及附属顶点集合所对应的树节点集合，根据最小权重特性和权重传播机制对矮状树分解中树节点对应的边的权重、树节点与附属顶点集合所对应的树节点集合之间的权重进行更新，同时对所有树节点的耗时数组以及子孙表进行更新。5.根据权利要求2所述的一种动态路网上基于树分解的knn查询方法，其特征在于，所述树节点的子孙表中设置一个哨兵sen，所述sen用于记录更新前进行knn查询时子孙表所遍历到的最短路网耗时标签位置，当道路无向加权图的权重改变时，通过查看子孙表中sen前受影响的最短路网耗时标签进行增量查询。

技术总结
本发明公开了一种动态路网上基于树分解的kNN查询方法，包括获取道路网络数据集，根据道路网络数据集构建道路无向加权图，所述道路无向加权图包括顶点集合、边集合以及权重集合，根据道路无向加权图中构建树节点，将连接后的树节点集合作为矮状树分解，对矮状树分解的每个树节点进行编号并获取所有树节点的祖先数组、耗时数组以及子孙表集合，获取待查询顶点，根据矮状树分解获取待查询顶点的最近邻集合。在保证kNN查询的正确性的前提下，极大提高了查询时间和效率。高了查询时间和效率。高了查询时间和效率。


技术研发人员：白梅 南彦鑫 王习特
受保护的技术使用者：大连海事大学
技术研发日：2023.07.17
技术公布日：2023/10/15