ICDE 2022 | 可感知工作负载的路网最短路径距离查询

时空实验室 2023-01-23

566

最短路径距离计算在实际生活中有着广泛的应用，例如自动驾驶、地图导航和路线规划等。然而在处理最短路径距离查询的时候，却有诸多因素限制算法的性能。尽管现有的算法已经克服了其中某些因素的影响，能够较为高效地处理最短路径距离查询，但仍存在着其他因素（例如查询请求空间上的分布不均）限制着算法性能的进一步提升。本次为大家带来数据库领域顶级会议ICDE 2022的论文：《Workload-Aware Shortest Path Distance Querying in Road Networks》。

一、背景

随着具备GPS功能的智能手机的普及，城市中的GPS设备几乎无处不在。与此同时，城市中的交通需求也在不断扩大。面对这一市场需求，许多科技公司都开始运营自己的网约车平台，并研发高效的最短路径距离查询算法以提升效率和自身竞争力。在最短路径距离查询研究中，其中一项挑战就是处理大规模的最短路径距离查询。在现有的研究成果中，有的方案（例如ALT，TNR等）通过构建可拓展索引以提供辅助数据结构支持，进而加速查询，但是这种方法在大规模道路网络中会造成大量的额外空间开销；而另一些基于2-hop labeling（2-hop labeling是一种为道路网络中每个顶点构建一个用于辅助计算的标签，从而使得最短路径距离计算只需要线性检索标签的技术）的方案通过减少标签的大小降低空间开销，但是这些方案都没有为大规模查询工作优化，所以在面对上述挑战时也没有优势。论文通过观察一份来自纽约的数据集，发现了两个查询工作的时空规律（如图1）：其一是空间分布不均，1%的查询顶点占总工作量的92.96%，剩余的99%的顶点仅占查询工作量的7.04%，这说明存在高频查询点；其二是时间本地性，在03:00 – 07:00查询频率普遍较低，而在08:00 – 13:00查询频率普遍较高，这说明大部分顶点在邻近时间段内的查询频率是相似的（这一点可以用通勤高峰期以及非高峰期解释）。

基于以上观察结果，论文提出了一种结合 wPLL 和 wH2H 的混合标签索引构建方案 WCF 以及基于强化学习的时间间隔分区方法 RL-TIP。wPLL与wH2H分别是PLL与H2H的改进版本，二者通过加入查询频率影响因子改变原方法的顶点标签索引结果以及树分解结果。PLL与H2H都是与2-hop labeling有关的技术，其中PLL通过计算拓扑中心性给每个顶点分配标签；H2H则通过树分解方法重建道路网络，二者都能有效提升最短路径距离查询的效率。

图1现实世界的查询工作特点

二、相关定义与概念

2.1 道路网络

道路网络（如图2）是一个有权图G=(V, E, W)，其中V是顶点集，E是边集，W是一个从边集到正实数集的映射，即W: E → R⁺。

图2道路网络的无向图示例

2.2 最短路径距离

给定一个起始点s和一个目标点t，定义SP(s, t)为从s到t边权重和最小的路径（即：最短路径），Dist(s, t)为SP(s, t)的边权重和。以上图为例，选取v₉为起始点，v₉为目标点，那么从v₃到v₉的最短路径SP(v₃,v₉)=(v₃,v₁₅,v₉)，最短路径距离Dist(v₃,v₉) = 2。

2.3 最短路径距离查询

定义q(s, t)为从起始点s到目标点t的最短路径距离查询，q(s, t)接受起始点s和目标点t作为参数，返回最短路径距离Dist(s, t)。

2.4 2-hop labeling

2-hop labeling是一种广泛应用于最短路径距离计算的技术。简要地说，2-hop labeling为每个顶点分配一个标签L(v)，L(v)包含一个键值对集合，并且键值对的形式为(o, Dist(s, t))。此外，2-hop labeling称标签在键域的投射称为hop，即: hop(v)={o│(o,Dist(v,o))∈L(v)}；称标签在值域的投射为spd，即：spd(v)={Dist(v,o)│(o,Dist(v,o))∈L(v) }。为了保证查询处理的正确性，所有分配的标签都需要满足 2-hop覆盖特性：对于任一顶点对s和t，s和t的标签交集至少包含一个hop o在s到t的最短路径上。如若给定一个最短路径距离查询，那么最短距离

。通过这种方法求解最短路径距离的时间开销为O(|L(s)|+|L(t)|)。

以下图为例，选取v₃为起始点，v₉为目标点，为了计算从v₃到v₉的最短路径距离，首先计算v₃与v₉的hop集交集hop(v₃)∩hop(v₉)={v₁,v₃}，然后就可以计算得v₃到v₉的最短路径距离Dist(v₃,v₉) = min{3 + 5, 0 + 2} = 2。

图3 wPLL构建的标签索引（左列为顶点，右列为标签，对应的道路网络为图2）

2.5 树分解

树分解（如图4）是图论中一种将图映射到树的方法，可用于加速解决某些图上的计算问题。下面展示如何利用树分解求解最短路径距离查询。

设T为道路网络G=(V, E)的树分解， V_T为T的节点集合，T的每个节点表示为X(v)(v∈V)∈V_T，X(v)包含V的一个子集，并且还满足这些条件：

(1) ∪X(v) = V；

(2) 对于E中的每条边(u, u’)，总存在一个节点X(v)满足u,u'∈X(v)；

(3) 对于V中的每个顶点u，集合{X(v)|u∈X(v)}构成T的一个连通子树。

同时，为了满足最短路径距离查询需要，每个节点X(v)还有两个对应数组作为辅助计算数据，其一是位置数组pos(v)，该数组记录每个u∈X(v)在T中的高度；其二是距离数组dis(v)，该数组记录X(v)到它的所有祖先节点的距离。

那么这样的树分解有两个特性：

(1) 令LCA(s, t)为X(s)和X(t)的最低共同祖先，则对于任意两个顶点s,t∈V，最短路径SP(s, t)至少经过LCA(s, t)的一个顶点；

(2) 给定一个T中的节点X(s)，对于任一v∈X(s) \{s}，X(v)是X(s)在T中的一个祖先节点。

利用这两个特性，最短路径距离可以用该公式计算得到：

。

以下图为例，假设有一个最短路径距离查询q(v₁₂,v₂₂)，首先求解LCA(v₁₂,v₂₂)=X(v₂)，然后得到pos(v₂)={1,2,3}，最后计算Dist(v₁₂,v₂₂)=min{8+8,6+6,1+1} = 2。

图4 使用wH2H方法构建的树分解（对应的道路网络为图2）

三、问题定义

设cost(q_i)为q_i的查询时间开销，单次工作量为Q={q_i}，V_Q为Q的顶点集，f_v为v∈V_Q的频率，那么单次工作开销为

论文的目标就是通过优化标签大小和利用顶点查询频率分布构建索引最小化该开销。

四、方法介绍

4.1 框架总览

论文提出的框架主要包括三个核心组件（如图5）：

(1) 工作负载预测模块：使用深度学习模型GraphWaveNet来根据历史查询记录预测实际OD查询对（OD是一个相关领域的术语简称，全称为Origin – Destination）的分布，并将其转换为顶点的查询频率分布；

(2) 可感知工作负载索引构建模块：基于工作负载预测模块的预测结果为道路网络顶点构建标签索引，该模块是论文的主要工作；

(3) 最短路径距离查询处理模块：将实际查询工作作为输入，返回查询结果。

图5 总体框架

4.2 wPLL

PLL是一种基于顶点序的标签索引构建方法，并且其顶点序计算只考虑拓扑中心性。按照顶点中心性降序处理顶点，PLL能够高效地计算出每个顶点的较小标签索引。然而，实际查询的频率分布是不均匀的，只考虑拓扑中心性也就忽略了这一点。所以论文在PLL的基础上提出了一种既考虑中心性，又考虑查询频率的wPLL方法（如图6）来构建标签索引。

从图的特点来看，中心性高的顶点往往能够覆盖更多的最短路径；从PLL的特点来看，中心性高的顶点通常标签索引更小。所以为了优化高频查询顶点的标签索引大小，论文提出了新的顶点序计算方程：σ(v)=β⋅f_v^*+ (1 - β)⋅b_v^*，其中f_v^*是顶点v的查询频率的归一化结果，b_v^*是顶点v的介数中心性的归一化结果，参数β 用于平衡中心性和查询频率的影响效果。

此外，由于在度数中心性、接近中心性和介数中心性中介数中心性对于PLL的顶点序计算是最高效的，在计算介数中心性时论文选择了SamPG方法，而其余的标签的生成方法则与PLL方法一致。

图6 wPLL构建的标签索引示例（左列为顶点，右列为标签）

4.3 wH2H

H2H是一种基于树分解的标签索引构建方法，其主要思路是按照度数升序处理每个顶点v并为其创建对应的节点X(v)，这种创建节点的方法也称为MinDegree方法。与PLL相似，H2H在创建节点时只有单一考虑因素，并不会考虑到查询频率分布的影响。所以论文在H2H基础上提出了既考虑度数也考虑查询频率的wH2H方法（如图7）。

wH2H使用MinImp方法构建索引，其主要思路与MinDegree方法相似，按照顶点重要性升序处理每个顶点v并为其创建对应的节点X(v)。顶点重要性可以通过该公式计算得：

，其中d_v^*=d_v/ d_max，γ是平衡参数，B_i是v_i所属的区块。此处提到的区块是由论文提出的区块分区技术生成的，之所以引入区块分区技术，是因为如果像σ(v) = γ⋅fv^* + (1 - γ)⋅d_v^*这样直接地引入频率参数，将会导致生成的树分解高度和宽度都比原MinDegree方法生成的大，从而造成额外空间开销。引入区块分区技术之后，所有顶点被分成N = ⌈n/η⌉个区块，每个区块的最大大小为η，然后区块按照由度数和查询频率决定的顺序处理，对于一个区块内的顶点，则按照顶点度数的顺序处理。

图7 wH2H构建的树分解示例

4.4 WCF：混合索引构建方法

上述提出的wPLL方法和wH2H方法在构建索引时的表现各有优劣，以下是二者的比较：

(1) 空间开销：给定一个树宽为ω的道路网络G，wPLL的空间开销为O(n⋅ωlogn)，wH2H的空间开销为O(n⋅h)，并且树高h通常比ωlogn大。

(2) 索引构建时间开销：wPLL的时间开销为O(ωmlogn+ω²nlog²n)，wH2H的时间开销为O(nhω + nlogn)，并且wH2H的树分解很快，由上而下的距离计算可以减少开销。所以在索引构建时间开销方面，wH2H是优于wPLL的。

(3) 查询开销：对于短距查询，wH2H更快；对于长距查询，二者的表现几乎一致。

(4) 应用适用性：wPLL更适合高度数的复杂图，而wH2H更适合低度数图。

为了综合二者的优势，论文提出了WCF混合索引构建方法，WCF使用wPLL处理高频查询顶点来降低查询开销，使用wH2H处理低频查询顶尖来减少索引构建开销。

为了构建WCF索引，论文提出了一种Core – Forest联合结构（如图8），其中Core结构的索引使用wPLL方法构建，而Forest结构的索引使用wH2H方法构建。对于高低频顶点的分割，论文设定了一个参数α来分割排序后前α%为高频顶点，剩余顶点则为低频顶点。

图8 Core – Forest 结构的标签索引示例

而为了构建Core-Forest联合结构，论文提出了RelaxedMinDegree方法来做树分解，以下是该方法的伪代码：

此外，论文考虑到如果查询起始点和目标点都是低频顶点，那么查询过程势必需要遍历边界顶点处理它们的标签，从而增加了查询过程的时间开销。所以论文提出了WCF-Variant方法（如图9），该方法将标签处理并行化于预处理流程中，从而只需要牺牲极少的预处理性能加速查询处理。

图9 WCF-Variant方法中的标签示例

4.5 RL-TIP：基于强化学习的时间间隔分区方法

为了更好的利用最短路径距离查询中的时间分布特性，论文首先将时间间隔分区问题抽象为马尔科夫决策过程，其关键元素如下：

状态：用于决策的状态量是一个五元元组s = (t_j, ρ^*, ρ_j, D_j^*, C)，其中t_j是当前的时间段，ρ^*是时间段t^*的所有顶点的查询频率（t^*是最新构建的标签索引所在的时间段），ρ_j是时间段t_j的所有顶点的查询频率，D_j^*是t^*的查询频率分布与t_j的查询频率分布的Jensen-Shannon散度，C是已获时间段的数量。

动作：一个动作a∈{0, 1}是一个决定是否分区的指示器。当a=1时，在时间段t_j处分区得到一个时间间隔[t^*, t_j_-1)，并基于t_j的频率分布创建一个新的标签索引；当a=0时，则不分区。

奖励：奖励代表了对应行动的质量，定义奖励为r_j=-∑_vi_∈_Vf_i,j⋅cost^*(v_i)，此处f_i,j为v_i在时间段t_j的查询频率，cost^*(v_i)是基于在t_i所构建的索引v_i的查询开销。

转移：转移是一个四元元组(s, a, s’, r)，代表在状态s下做出行动a，接受奖励r，并移动到下一状态s’。

解决这个马尔可夫决策过程的目标就是通过深度学习技术学习一个用于决策的action-value函数，这个函数将状态信息作为输入，输出行动的值，然后选择具有最大值的行动。

所以论文提出了RL-TIP算法来训练一个DQN神经网络去评估这个action-value函数Q(s, a; θ)。

五、实验

5.1 实验设定

数据集：（如图10）其中HK、MH、CD以及NY的数据是从真实历史数据中提取的，而FL和CA的数据基于原有数据的规律合成的。

图10 数据集图表

性能评价标准：平均查询时间；索引构建时间；索引大小。

5.2 自评估

参数研究：（参考图11(a)-(c)）1. WCF的索引大小以及索引构建时间随着ω_max的增加而增加，与此同时平均查询时间先减少后增加，其原因是ω_max会影响Core-Forest结构的规模，进而影响到综合的查询时间。对于参数β与γ，其趋势以及造成该趋势的原因都与ω_max类似；2. 对于参数η，当η大于1的时候各方面开销都没有明显增加，证明了论文提出的区块分区方法的有效性。

基于非均匀分布的参数选择：如图11(e)，对于不同的工作情况，论文每次调节β至查询表现最佳，结果展现了β值的有效性，给定一个查询工作情况，总能设定一个合适的β值达到优化目的。

α效果：当α为100%时有最佳查询性能表现，所以论文默认设定α为100%，这样可以避免超参数调节以及顶点排序开销。

图11参数分析

5.3 利用时空分布规律

K值选择：如图11(f)所示，在K=5之前，查询时间随着

值的增加而急剧降低，但是在K=5之后降低非常缓慢，所以论文默认设定K为5。

查询时间： wPLL+、wH2H+和WCF+分别是wPLL、wH2H以及WCF的带RL-TIP版本。如图12所示，我们可以观察到WCF和wH2H在所有数据集中都优于其他方案，并且相较于PLL，wPLL+、wH2H+以及WCF+都分别有28.9%、53.8%和62.3%的平均提升比率，相较于H2H则平均提升比率为9.4%、41.4%和51.4%。此外，对于没有RL-TIP的基本方案，wPLL+、wH2H+和WCF+的查询时间分别减少19.6%、31.7%和41.7%，这说明考虑时空分布规律比仅考虑空间分布不均更佳。

图12 平均查询时间比较

索引开销：如图13，wPLL+，wH2H+和WCF+的索引大小分别大基础版本的5倍，4.5倍以及4.2倍。

图13 RL-TIP的索引大小

六、总结

总的来说，论文提出了一个利用查询工作的时空分布规律加速道路网络最短路径距离查询的解决方案。首先，论文拓展了现有PLL和H2H索引方法，提出了wPLL和wH2H方法。基于这些，论文又提出了能够结合wPLL和wH2H优点的混合索引构建方法WCF。然后，论文为了使得基于上述方法构建的索引能够不断适应实际的查询规律，提出了RT-TIP时间间隔分区方法。实验数据表明，wPLL，wH2H以及WCF都有不俗的性能表现，相较于PLL和H2H，WCF的索引大小以及索引构建时间都有较大的提升。

-End-

本文作者

陈泽超

重庆大学物联网工程专业在读二年级本科生，重庆大学START团队成员。主要研究方向：时空数据流式查询。

时空艺术团队（START，Spatio-Temporal Art）来自重庆大学时空实验室，旨在发挥企业和高校的优势，深入探索时空数据收集、存储、管理、挖掘、可视化相关技术，并积极推进学术成果在产业界的落地！年度有2~3名研究生名额，欢迎计算机、GIS等相关专业的学生报考！

最短路径中心频率时间计算索引 hop

文章转载自时空实验室，如果涉嫌侵权，请发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。

ICDE 2022 | 可感知工作负载的路网最短路径距离查询

评论