近年来，随着现代综合化交通运输体系结构的改变，无线通信网络安全的快速发展，具有定位功能、提供地图服务的设备在物联网中被广泛应用[1-3].利用基于位置服务来获取从指定源点到目标点的最短路径查询结果已经逐渐成为主流的查询方式.尤其是面临紧急情况出行时，人们往往选择旅行时间最短的路径作为行驶路线，但是现实世界道路网中街道旅行时间具有时变性，交通状况并不稳定，会面临道路临时修建、雷雨天气等突发事件，导致街道的旅行时间发生动态的改变.尽管已经存在许多求解最短路径的方法，但是能否高速有效地实现检索动态道路网中旅行时间不确定的最短路径仍面临如下问题：
1) 查询结果的时效性与查询请求响应速度的平衡问题.文献[4]提出无索引方法，在保证路径权重有效的情况下，通过服务器计算2点之间成本最小的路径，但在非大规模图上执行路径查询仍需花费几秒钟，其查询性能有待提高.为解决查询耗时长的问题，文献[5]提出预构建全局索引的算法，以加速最短路径查询.虽然引入全局索引的查询技术能够快速响应查询请求，但索引维护开销较大，将面临索引未完成更新，路况就可能发生了新的变化的情况，导致查询结果不适用路况而变得无效.
2) 查询响应速度与服务器工作负载的平衡问题.当道路网处于查询高峰期时，查询请求的峰值可达百万次[6]，此时服务器将产生极高的工作负载、延迟查询的响应时间.虽然可以通过部署更多的服务器解决负载过高的问题，但成本昂贵，并非所有公司都可以承担.该挑战在可以保证查询结果有效性的无索引算法中尤为突出.为提高大规模路径的查询效率，可利用缓存中的数据来提升查询请求的响应能力，减少服务器工作负载.文献[7]通过引入缓存技术启发式地将动态图中收益值最大数据替换缓存中无效路径来提高缓存命中率，加速查询效率.然而该方法只适用于单路径更新的场景.文献[8]利用历史日志信息将查询频率高的数据预加载到缓存来提高缓存命中率.而复用历史日志信息中的高频路径来构建缓存，并不适用于时变道路网场景，主要是因为过往数据不具备时效性，不能应对动态变化的场景，导致缓存命中率降低[9]，命中的路径也因数据失效而出现结果偏差，继而影响用户体验.
例如，在偏远地点A开设一场万人以上的大型演唱会，那么在演唱会当天会存在上万次前往地点A的路径查询请求.若是基于历史信息的缓存策略，偏远地区的数据不会预存入缓存，缓存则不会命中有关地点A的查询请求，从而只在代理服务器中执行查询.此时，若出现大量与地点A相关的查询，将导致服务器负荷骤增，系统整体的查询性能变差.若此时提供一种可以实时识别查询频率高的路径并用来替换缓存中的低效的路径，则可以有效地避免上述情况的发生.意味着在演唱会当天，缓存中的数据能够及时且有效地应答多条前往地点A的路径查询请求，以减少代理服务器的计算量.此外，当地点A的查询频率变低后，缓存中与A相关的数据则会自动被其他高频率数据置换.
通常采用15 min为一个时钟间隔来更新缓存数据[10]，该方式得以有效应用，是因为一段时间内路况的变化非常小，短时间内可以维持命中路径的准确性.因此采用实时更新缓存数据的方式不仅可以提高缓存命中率，减少服务器的运行成本，还可以提高命中数据结果的有效性.
综上分析，在具有时变特征的道路网中，一个良好的基于缓存的最短路径查询算法是能够支持最短路径快速查询和提高缓存命中率的必要条件.因此，本文设计了一个尽可能最大化利用缓存的算法来支持最短路径查询.并在缓存存储策略中，将路径共享能力计算方法和差异多样性技术相结合，用于减小缓存中冗余数据的占用容量，提高缓存命中率.此外，缓存中的数据存储结构具有数据弱相关、结构紧凑的优点，不仅可以减少数据的存储空间，还可以实现动态数据的快速维护、加快路径的检索速度.
本文主要贡献有3个方面:
1) 提出的新缓存存储结构包含用于存储节点的邻接点索引、记录路径节点的位图索引以及记录路径基本信息的路径信息索引.该结构新颖之处在于其存储空间较小，索引间可独立地维护缓存中的数据;
2) 提出一种缓存存储策略，其不仅显著地减少了缓存中的冗余数据，还可以有效且实时地识别出存入缓存的最短路径，以提高缓存命中率.
3) 提出了基于缓存的时变道路网最短路径查询算法(cache-based time-varying shortest path query, CTSPQ).其巧妙地借助缓存存储结构的特性，提高了最短路径在缓存中的查询速度.
在真实的数据集上进行大量实验，验证了本文提出的策略以及查询方法的有效性.
1 相关工作
1.1 最短路径查询
近年来，最短路径查询问题被广泛应用在各行各业，其变体问题被广泛用来研究，如查找从给定源点到目标点最短路径的单源点对(single pair shortest path, SPSP)问题、查找给定顶点到图中每个顶点最短路径的单源点(single source shortest paths, SSSP)问题[10]以及查询图中所有顶点最短路径的全对(all-pairs shortest path, APSP)问题[11].但是在道路网中检索最短路径的花费时间仍旧高，如常用的Dijkstra算法的时间复杂度为O(m+n log n).
为解决大规模网络上最短路径查询耗时长的问题，文献[5,12-17]提出了支持快速检索最短时间/油耗/距离路径问题的索引结构，缩小了最短路径查询理论与实践之间的差距.文献[14]设计的HoD(highways-on-disk)索引结构通过采用较小的I/O消耗成本来回答单原点距离(single source distance, SSD)和SSSP等查询问题，但HoD仅适用于数据变换频率低的情况.文献[15]通过使用关系数据库管理系统解决了SSSP查询慢的问题，但是当网络中的数据或者结构发生变化时，该方法将耗较长的时间重新计算节点之间的关系.
文献[16]给出了维护索引结构时间复杂度的理论上下界，最优下界与网络中顶点数量呈线性关系，但在节点数量非常庞大的网络中才能表现出线性优势。文献[17]利用随机化技术提出了一个有效预测路径距离的方法.是通过以空间换时间的方法来构建索引，虽然可以通过部署大量服务器提高查询速度，但运行成本高、可扩展性较差.
1.2 缓存管理
缓存具有快速交换数据的能力，文献[18-25]利用缓存技术减少大规模最短路径查询时间.即预先构建一个缓存区，若缓存中的数据能够直接应答查询请求并返回结果，则无需采用代理服务器计算路径，从而加快系统整体的响应速度.故利用缓存加速查询的关键点在于查询请求在缓存中命中率.
现有提升缓存命中率的策略主要有3种：动态缓存策略、静态缓存策略及混合缓存策略.静态策略将根据历史日志中查询频繁的路径对缓存进行更新，该策略的数据无法应对突发事件，不适用于本文.动态策略包括最近最少使用(least recently used, LRU)和最不经常使用(least frequently used, LFU)等，LRU策略是将新路径置换缓存中最近最久未使用的路径的策略，LFU策略则是将当前时间使用次数最多路径置换缓存中使用次数最少的路径，以此来提高缓存命中率.文献[19]设计了最短旅行时间的路径缓存(shortest travel-time path cache, TPC)算法，用于计算时变道路网中旅行时间最短的路径，但路径能否加入缓存依赖于缓存已有节点.文献[20]提出的最短路径缓存(shortest-path-cache, SPC)方法，虽然能回答查询频繁高的路径，但面对突发状况时的查询将不具备稳定性.混合缓存策略将静态策略和动态策略相结合来更新缓存[21].
除此之外，文献[22]利用寄存器设计了通用的框架来生成时序关键路径，减少了相同查询请求的计算次数，但其存储空间较小.文献[23]引入的Cache-Oblivious模型为多级内存系统设计算法提供了理论基础.该模式是专门为标准的两级I/O模型设计的算法，但需要小心地调优它们所运行的系统的参数.文献[6]提出了批量处理最短路径的算法，首先将查询请求生成云状查询集，再利用缓存统一查询以减少查询次数.文献[8]不仅考虑了日志路径的查询频率，还通过路径的覆盖范围来衡量最短路径的影响力，将高影响力的路径存储入缓存，进而提高其命中率.文献[24]设计了路径缓存规划系统，将缓存中部分匹配的查询请求结果的路径作为返回用户端路径的子路径段，以此减少服务器对整条路径的计算量.文献[25]不再关注网络节点之间的组织情况，而是通过边来构造路径缓存，首先定位查询请求点在缓存中的候选边，由边之间连接得到最短路径.虽然上述缓存技术[18-25]可以加速最短路径查询、平衡索引维护的时间和路径查询速度的关系，但仅有少部分文献涉及时变道路网中最短路径查询的缓存策略，因此在高度动态网络中，利用缓存设计高速、有效应答路径查询方法变得十分重要.
1.3 基于差异多样性的路径规划
提高缓存命中率的常规方法是将高频率路径加入缓存，但高频路径往往存在大量重复路径段.为减少冗余数据存入缓存，本文采用差异多样性技术来避免缓存存储大量相似的路径.现在有关差异性的研究多集中在数据新颖度[26]，或者多目标空间Skyline查询[27]的问题上，但不适用于本文的场景.虽然也有学者研究路径多样性问题，但并不能完全移植到当前问题，因为在道路网中求解具有差异多样性的路径是一个NPC问题，除此之外，在不同场景下处理数据方式不一，时间复杂度也不相同[28].
文献[29-30]基于阈值剪枝策略来测量路径的差异多样性，以此减少路径查询以及比较路径之间相似性的次数.其中，文献[29]结合阈值约束条件，返回K条不仅可以兼顾查询结果总得分还能兼顾查询结果多样性的数据，既除掉了结果集中相似的数据又保证了结果的质量.但这种用精确查找的方式来获取最优结果的耗时较长，与本文提高用户响应速度的目标背离.文献[30]通过结合相似度阈值精心地设计了算法的下界，以计算从查询源点到目标点的前Top-K条不相似的最短路径，有效地减少了搜索空间并显著提高了效率.
不同于文献[29-30]，本文在引入差异多样性策略的同时，采用贪心思想实现最大化存入缓存的K条最短路径的收益，进而减少服务器的计算量.其中存入缓存的K条路径来自不同查询结果，是互不相关的路径集合，这些路径既存在差异性，又存在共同节点，便于路径紧密联系.此处，缓存中的路径数量K并非固定数值.
2 定 义
本节重点介绍基于缓存的时变道路网最短路径查询的相关理论.表1描述了基本符号.
Table 1 Summary of Notation
表1 符号概要
符号描述G无向时变道路网v(lat,lng)具有地理空间坐标(lat,lng)的节点vQs,t节点vs到vt的查询请求P,Ps,t节点vs到vt的最短路径P,具体表示为Ps,tJPath(vs,vt)节点vs到 vt的连接路径表示为JPath(vs,vt)C缓存Cψ缓存C中最短路径的集合Sim(Ps,t,Ps',t')路径Ps,t,和Ps',t'的相似度τ相似度的约束阈值distE(vs,vt)节点vs到vt的欧氏距离θ路径欧氏距离比的约束阈值Tmax路径在缓存C中可滞留的最长时间ShP最短路径P的共享能力
2.1 基本定义
定义1. 时变道路网模型.时变道路网G=(V,E,W,T)，其中V 和E分别表示G的节点集和边集，节点v∈V，边e=(vi,vj)∈E，函数W:E×T→RV表示边集E在时刻T的权重映射函数，其中边e=(vi,vj)的时间权重为w(vi,vj).
定义2. 最短路径.给定道路网G=(V,E,W,T)，G上从vs到vt的所有路径中，具有最短旅行时间的路径P，被称为最短路径Ps,t，其中节点vs,vt∈V.
Ps,t是由一组从vs到vt的有序边(或点)组成，表示为Ps,t=〈v0→v1→…→vn〉，其中v0=vs，vn=vt，Ps,t的旅行时间为
本文用vi∈Ps,t表示节点vi在路径Ps,t上.
定义3. 查询请求.在道路网G=(V,E,W,T)上，由用户终端发出查询请求Qs,t，用于查询从vs∈V到vt∈V的最短路径Ps,t.其中vs称为Qs,t的查询源点，vt称为Qs,t的查询目标点.
定义4. 缓存空间容量.给定缓存C，C中所有最短路径的集合为ψ.其中，C的空间容量为|C|，C中数据的占用空间为|ψ|≤|C|.
定义5. 完全命中、部分命中及未命中.给定缓存C和查询请求Qs,t,完全命中表示C的最短路径集ψ中至少存在一条包含节点vs,vt的最短路径，完全命中的路径集可形式化为
ц(Ps,t)={Pi,j|(vs∈Pi,j)∧(vt∈Pi,j)∧ (vs≠vt),Pi,j∈ψ}；
部分命中表示ψ中至少存在一条包含节点vs或vt的最短路径，部分命中vs的路径集可形式化为
ц(vs)={Pi,j|(vs∈Pi,j)∧(vt∉Pi,j),Pi,j∈ψ}；
否则称为未命中，即ψ中不存在包含节点vs或vt的最短路径P，未命中可形式化为
∀P∈ψ,(vs∉P)∧(vt∉P)∧(vs≠vt),
其中，完全命中意味着ψ中至少存在一条最短路径的子路径作为Qs,t的结果.由文献[20]提出的最优子路径性质可知，最短路径的子路径也是最短路径，故完全命中获得的路径可以保证命中结果的准确性.
定义6. 连接路径.给定最短路径Pi,j和Pi′,j′，节点vs,vm∈Pi,j，vt,vm∈Pi′,j′，存在子路径〈vs→…→vm〉⊆Pi,j和〈vm→…→vt〉⊆Pi′,j′,⊆表示路径间的包含关系.通过vm连接2条子路径组成一条从vs到vm再到vt的新路径，该路径称为连接路径JPath(vs,vt)=〈vs→…→vm→…→vt〉.
其中连接路径JPath(vs,vt)可近似为最短路径Ps,t，用于应答查询请求Qs,t，减少服务器的计算量.
2.2 问题定义
本节给出CTSPQ问题的形式化定义.
定义7. CTSPQ(G,vs,vt,C,T,Tmax).给定节点vs,vt∈G，C为时刻T的缓存，Tmax为每条最短路径在C中滞留的最长时间.
记ψ为时刻T之前存入C的n条最短路径集合，Ω为时刻T待存入C的m条最短路径集合，ShPi为Pi∈(ψ∪Ω)的共享能力，tPi为Pi存入C的时刻.0-1变量xPi表示Pi是否存储于C中，xPi=1表示Pi存于C中，xPi=0表示Pi未存C中，并记X=(xP1,xP2,…,xP(m+n)).
CTSPQ的目标是最大化缓存C中最短路径集ψ的收益Bmax(ψ,Ω,T,Tmax)，并以在线的形式在C中快速规划出一条从vs到vt的最优最短路径Ps,t，使得服务器的计算量最小.其中，Bmax(ψ,Ω,T,Tmax)满足：
(1)
缓存技术之所以能提高路径查询速度是因为其可以降低服务器对数据库的读操作.因此，能否较好地解决CTSPQ问题取决于C中ψ的收益，即缓存收益越大，命中越高.此外，加入缓存C的路径数量有限，若C中的数据无法应答从vs到vt的查询请求，则可从服务器中查询并获取最短路径Ps,t.
由式(1)可知，求解缓存最大收益问题的时间复杂度为O(n|C|)，是一个伪多项式问题.其计算成本较高，因此本文将采用贪心思想计算缓存中数据的最大收益，以减少构建缓存的计算时间.
3 基于缓存的时变最短路径缓存查询算法
本节首先介绍基于缓存的时变道路网最短路径查询算法CTSPQ的总体框架.如图1所示，框架包含3个模块：查询请求检测模块、最短路径评估模块和缓存管理模块.首先从用户终端发出具有真实地理坐标源点vs(lat,lng)和目标点vt(lat,lng)的查询请求Qs,t(步骤①)；通过查询请求模块将vs(lat,lng),vt(lat,lng)映射为节点vs,vt∈G，以转化为G上的查询请求，继而从缓存C中获取Qs,t完全命中或部分命中的路径作为候选路径集(步骤②～④)；然后，在最短路径评估模块判断候选路径集中是否存在有效应答Qs,t的路径，若是则将一条近似最优的路径返回用户终端，否则从代理服务器检索Qs,t的最短路径，并返回到用户终端(步骤⑤～⑧)；此外，缓存管理模块中的缓存结构用于存储数据，缓存存储策略决定从服务器获取的实时最短路径是否能存入C(步骤⑨～⑩).
Fig. 1 CTSPQ schematic diagram
图1 CTSPQ框架示意图
3.1 缓存管理模块
构建索引是加速最短路径查询的主要技术之一，在数据的检索和存储中起着重要作用.因此本文在本模块中设计了便于更新缓存数据的索引结构以及提高缓存命中率的路径缓存存储策略，以快速响应时变环境下的查询请求，减少服务器的工作负载.
如图1所示，无论执行哪个模块，只要执行操作皆离不开缓存中的数据.即一旦触发其他模块，缓存管理模块也随之触发.
3.1.1 缓存存储结构
图2展示了一个简单缓存最短路径的例子.根据图2(a)的子图得到了图2(b)的5条最短路径，并按照路径节点的旅行顺序将路径存入缓存列表，如路径P4,3=〈v4→v6→v5→v3〉存放节点的顺序为v4,v6,v5,v3.当存在查询请求Qs,t时，首先判断缓存列表中的路径是否存在从由vs到vt的子路径，若是则直接应答Qs,t.如查询请求Q4,7可由图2中的P2,4应答.虽然此存储方式可应答查询请求，但会导致缓存出现大量的冗余数据，如v1存储了3次，v2存储了4次，甚至出现了冗余路径，如P1,4是P1,6的子路径.
Fig. 2 An example of simple cache storage
图2 简单缓存实例图
Fig. 3 An example of the AMPS storage path
图3 AMPS存储路径示意图
因此，为减少数据的存储空间，本文设计了一个数据弱相关、结构紧密的缓存存储结构.该结构由存储节点的邻接点索引(adjacency node index, ANI)、存储路径的位图索引(bit map index, BMI)以及记录路径基本信息的路径信息索引(path information index, PII)等3部分组成，并简称为AMPS.图3展示了以AMPS形式存储图2中5条最短路径的例子.
1) 邻接点索引ANI.
ANI记录了缓存C中每条路径节点的邻接点关系，记为邻接点对〈vi,vj〉，并为返回一条有序的最短路径做准备.其中，每个邻接点对在ANI中最多存储一次，表示C中至少存在一条从vi到vj(或从vj到vi)的路径.ANI引用了文献[8]的模型，它无需存储G上所有邻接点对关系，减少了冗余数据存入C.
以图3(a)为例，v2的邻接点有v1，v3和v4，存在路径P1,6,P1,5经过v2到达v3；P1,4,P2,7经过v2到达v4.虽无路径经过v2到达v1，但存在经过v1到达v2的路径P1,6,P1,4和P1,5，故ANI记录了邻接点对〈v1,v2〉的关系.
2) 位图索引BMI.
BMI以位图形式记录了最短路径P.如图3(b)所示，存在于路径上的节点用“1”标注，否则标注为“0”，其中路径P1,4=〈v1→v2→v4〉上的节点v1,v2,v4在BMI中被“1”标记.因为位图可以执行二进制操作，因此BMI可以快速识别查询请求的候选路径，并快速判断C中数据所涉及的节点.
以图3(b)为例快速识别Q1,3和Q3,7的候选路径.令操作BMI(v)表示求解节点v所在的路径集合，请求Q1,3通过执行BMI(v1)∩BMI(v3)={P1,6,P1,5}得到完全命中的候选路径集；而Q3,7执行BMI(v3)∩BMI(v4)=∅，无完全命中的候选路径集，但可以通过部分命中操作获取与源点v3和目标点v4相关的2个部分命中候选路径集BMI(v3)={P1,6,P1,5},BMI(v4)={P2,7}，根据候选路径集执行连接操作获得应答Q3,7的连接路径，即通过v2连接候选路径P1,6和P2,7获得答查询请求的候选连接路径JPath(v3,v7)=〈v3→v2→v4→v7〉.
3) 路径信息索引PII.
PII记录了ψ中每条路径P的基本信息〈tP，ShP〉，用于更新缓存C中的数据，以保证从缓存中得到有效的查询结果.其中tP表示P加入C的时刻、ShP表示P的共享能力(见定义8).利用tP计算P在C中滞留的时长，当时长超过Tmax时，从C中移除P； ShP用于判断P是否被新路径置换，因为路径共享能力是反映路径受欢迎程度和重要性的指标，是计算缓存收益的主要影响因素.
定义8. 路径共享能力.给定道路网G=(V,E,W,T)上的一条最短路径P=〈v1→v2→…→vn〉，P的路径共享能力记做ShP.归一化的ShP可形式化为
(2)
其中,0≤μ1，μ2，μ3≤1，μ1+μ2+μ3=1；QS为当前G中所有查询请求的集合，|QS|为QS中请求的数量；|QSi|为节点vi∈P在QS的源点集和目标点集中出现的次数；|di|为节点vi∈V的度数；|E|表示边E的数量；|V|为节点集V中节点的数量；P的节点数量为|P|=n.
道路网中的节点度数之和为边数的2倍，因此P上所有节点的度数之和
此外，QS中源点和目标点数量为2|QS|，P上所有节点同时在QS源点集或目标点集中出现的次数不超过2|QS|.因此P的路径共享能力可以进行归一化处理.
以图2举例说明路径共享能力的计算方法，记图2(a)为道路网子图G′，令图2(b)中最短路径的查询请求为查询请求集QS,μ1=0.4,μ2=0.2,μ3=0.4；故|QS|=5,|E|=7,|V|=7.若求解P1,6=〈v1→v2→v3→v4→v5→v6〉共享能力，可知
类似方法可得其余4条最短路径的共享能力见图3(c).
算法1展示了在时刻T将最短路径P加入缓存C的伪代码.假设P的共享能力为ShP，首先获取C中AMPS的数据(行①)；接着依次遍历P上的节点vi 及其邻接点vi+1∈P，并将2点添加至BMI,ANI中，其中，若ANI中已存在邻接点对〈vi,vi+1〉的信息，则无需对索引ANI进行操作(行②～④).最后将P的信息〈T，ShP〉存入PII，并返回C(行⑤～⑥).
算法1. 插入算法Insert(P,C,T,ShP).
输入：新路径P、缓存C、当前时间T、共享能力ShP；
输出：缓存C.
① ANI,BMI,PII←get(C);
/*从缓存C中获取索引信息*/
② for each node viin P
③ add(ANI,BMI,vi,v,P);/*分别在ANI,BMI中添加邻接点对〈vi,vi+1〉及路径vi∈P信息*/
④ end for
⑤ addPII(PII,T,ShP);
/*将P的信息加入PII*/
⑥ return C.
以图3为例，令T=1,|ψ|=0，此时向C中添加共享能力为0.511 4的最短路径P1,4=〈v1→v2→v4〉.首先从v1开始，在ANI中加入v1的邻接点v2，v2的邻接点v1，在BMI中用“1”标注v1∈P1,4；然后在ANI中加入v2的邻接点v4，v4的邻接点v2，在BMI中用“1”标注v2∈P1,4；循环上述步骤，直至用“1”标注v4∈P1,4；最后在PII中添加P1,4的信息〈1,0.511 4〉.
算法2. 删除算法Delete(P,C,T).
输入：删除路径P、缓存C、当前时间T；
输出：缓存C.
① Z←空栈,D←空集合;
② ANI,BMI,PII←get(C);
/*从缓存C中获取索引信息*/
③ v′←random(P);
/*随机获取P上的一个节点*/
④ Z.push(P,v′,D); /*将节点v′入栈Z*/
⑤ while 栈Z中存在元素时
⑥ v←Z.pop();
/*出栈Z中的元素放入v*/
⑦ if节点v′和v当且仅当存在于路径P
⑧ delete(ANI,v,v′ ); /*在ANI中删
除邻接点对〈v,v′ 〉的信息*/
⑨ end if
⑩ D.add(v)； /*记录已删除的节点*/
Z.push(P,v′，D)；/*将节点v′不在D
中的邻接点入栈Z*/
end while
delete(PII,BMI,P);
/*删除PII,BMI中P*/
return C.
如算法2所示，若从C中删除一条最短路径P，首先初始化栈Z，集合D，D记录已删除ANI中P的信息，Z记录P上待删除的节点(行①)；接着，获取AMPS中各索引信息，并任选一点v′∈P作为P的删除起点，根据ANI和BMI的信息，将v′在P上的邻接点入栈到Z，v′加入D(行②～④)；然后，出栈Z中待删除的节点v，若邻接点对〈v,v′〉当且仅当出现在P ∈ψ上，则删除ANI中〈v,v′〉的关系.接着v加入D.重复以上操作，直至Z中无任何元素.最后删除PII,BMI中与P有关的信息，并返回C(行⑤～).
3.1.2 缓存收益模型
求解缓存最大收益问题是NPC问题，本文首先采用简单的Baseline策略构建缓存数据.Baseline策略结合了贪心思想，将路径共享能力近似为路径存入缓存的收益，在保证在较高命中率的前提下，减少存储过程的计算量.Baseline策略首先按照待加入缓存的最短路径共享能力以从大到小的顺序依次加入缓存C，直到C中无多余空间存入新路径，因此Baseline的时间复杂度为O(n lg n).
以图4说明采用Baseline策略构建路径缓存C的方法.在道路网子图G′上，首先为方便计算C中数据的占用空间|ψ|，举例时仅考虑PII及ANI的占用空间.令一个节点的占用空间为1，一条PII信息占用空间为2，Tmax=6，初始化|ψ|=0，|C|=16.在T=1时，待加入C的3条最短路径的共享能力的大小依次是ShP1,6>ShP1,5>ShP5,7.故首先确定P1,6加入C需要在ANI中增加10个节点(5个邻接点对)，故将P1,6加入C时|ψ|=10+2<|C|；接着P1,5是P1,6的子路径，只需增加PII信息，加入C时|ψ|=12+2<|C|；最后判断P5,7加入C还需在ANI中新增邻接点对〈v6,v7〉，占用4个空间，而|ψ|+4=18>|C|，故P5,7不被加入C.此时缓存中的共享能力总和为0.861 9+0.695 2=1.557 1，并且可以应答路网上v1～v6之间的查询请求.
虽然采用Baseline策略可以减少构建缓存的计算量，但是无法避免子路径等冗余数据存入缓存，如P1,5是P1,6的子路径.然而道路网中访问频率高的路径，其子路径也往往具有较高的访问频率，这些子路径极易存入缓存.因此在第3.1.3节改进了Baseline策略.
Fig. 4 Example diagram of TSPC strategy
图4 TSPC策略实例图
3.1.3 改进存储策略
本节为优化Baseline策略提出了时变最短路径缓存(time-varying shortest path cache, TSPC)策略.该策略在Baseline的基础上结合了差异多样性技术，在保证缓存路径有效的前提下，尽可能使得缓存中的任意2条路径不相似，以减少缓存中的冗余数据，达到提高缓存命中率的效果.
衡量数据相似度常用的方法为Jaccard相似系数，但Jaccard适用于衡量路径重合度而差异性.故本文改进相似度度量方法来判断缓存路径的相似性.
定义9. 相似度度量.给定最短路径Ps,t和Ps′,t′以及相似度约束值τ，Ps,t和Ps′,t′相似度为
(3)
其中,|S(Ps,t)∩S(Ps′,t′)|表示 Ps,t和Ps′,t′具有一样节点的数目；min(|Ps,t|,|Ps′,t′|)表示Ps,t和Ps′,t′之中拥有较少节点数量的数值；τ的取值范围为[0,1].
与Jaccard略为不同，本文相似度度量方法选择min(|Ps,t|,|Ps′,t′|)作为分母，它可以清楚地感知较多节点数目的路径能够作为较少节点数目路经的共享路径.其中，τ值的大小决定缓存中路径间最高相似度，τ值越大冗余数据越多.
TSPC策略的最坏时间复杂度为O(kn+n lg n)，其中k表示|ψ|=k，n表示在时刻T待加入缓存的最短路径数量，O(n lg n)表示排序的时间复杂度，O(kn)表示构建k条互不相似最短路径的最大开销.而最优时间复杂度是O(n lg n)，即共享能力最大的前k条最短路径两两不相似.
以图4为例说明TSPC策略构建缓存C的方法.为方便与Baseline策略进行比对，TSPC的初始条件与Baseline一致，除此之外，令τ=0.7.当T=1时，首先对待加入C的3条最短路径按照其共享能力排序，即ShP1,6>ShP1,5>ShP5,7.由TSPC策略可知，先将P1,6加入缓存C，此时|ψ|=12<|C|；接着判断P1,5与C中路径集ψ的相似度，由Sim(P1,5，P1,6)=1>τ可知，C拒绝P1,5的加入；接着判断P5,7与C中ψ的相似度，即Sim(P5,7,P1,6)=2/3<τ，此时将P5,7加入C需在ANI中新增邻接点对〈v6,v7〉，占用空间为|ψ|+4=16≤|C|，故将P5,7加入C.虽然缓存的共享能力总和为0.861 9+0.523 8=1.385 7<1.557 1(Baseline策略1.557 1)，但缓存C中的数据不仅可以应答Baseline策略可应答的查询，还可以通过构建连接路径应答与v7有关的查询请求，提高了缓存的命中率.
此外，当T=7时，待加入C的2条最短路径的共享能力为ShP3,7>ShP2,4.首先由T-Tmax=1可知，在1时之前加入C的路径已逾时，故清空缓存C，|C|=0.接着将P3,7加入C，空间容量|ψ|=10<|C|，然后判断P2,4与C中ψ的相似度，Sim(P3,7,P2,4)=2/3<τ满足约束条件，还需在ANI中增加邻接点对〈v2,v3〉、PII中增加基本信息，|ψ|+4=14<|C|，故可将P2,4加入C.
算法3展示了以TSPC策略更新缓存的伪代码，假设在时刻T存在一条待加入缓存C的最短路径P.首先初始化优先队列Z，D，分别用于记录相似度大于τ、共享能力小于ShP的路径，根据式(2)计算P的共享能力ShP(行①～②)；接着遍历ψ中的路径，首先通过Tmax移除C中逾时路径，然后将ψ中相似度高于τ且共享能力低于ShP的路径入队Z，剩余共享能力低于ShP的路径入队D(行③～)；若除去C中与Z相关的路径数据后，C中还有剩余空间存储P，则以路径P置换C中与Z相关的路径(行～)；否则判断除去与C中相关的Z,D数据后，是否有多余的空间存储P，有则直接删除C中与Z相关的数据，然后按共享能力从小到大依次出队D中的路径，并从C中删除与该路径相关的数据，直至有C中有空间将P添加至C(行
～
)，否则不进行任何操作，最后返回C(行
).
算法3. TSPC更新缓存算法Update(C,P,T,Tmax,τ).
输入：缓存C、最短路径P、当前时间T、最大滞留时间Tmax、相似度阈值τ；
输出：缓存C.
① Z←空优先队列,D←空优先队列;
② ShP←根据式(2)计算路径P的共享能力;
③ for each Pi in C
④ if T-tPi≥Tmax
⑤ Delete(Pi,C,T,ShP);
/*删除路径Pi*/
⑥ else if Sim(Pi,P)>τ且ShPi<ShP
⑦ Z.push(Pi); /*将路径Pi入队Z*/
⑧ else if ShPi<ShP
⑨ D.add(Pi); /*将路径Pi 入队D*/
⑩ end if
end for
if |C|-|ψ+ P|>0
Delete(Z,C,T,ShP);
/*删除缓存C中与Z有关的路径*/
Insert(P,C,T,ShP);
/*将P加入缓存C*/
else if |C|-|ψ-D-Z+P|>0
Delete(Z,C,T,ShP) ;
/*将缓存C中与Z相关的路径删除*/
DeleteAndAdd(D,C,P,T,ShP);
/*出队D中的路径并删除缓存C与其相关的数据，直至缓存容量满足|C|≥|ψ+P|*/
end if
return C.
3.2 查询请求检测模块
本模块用于识别缓存中可应答查询请求的候选路径集.在位置坐标评估时需执行节点映射操作，是因为真实地理空间中的坐标是连续不断的，而现有的存储设备无法将所有坐标点存入存储设备，所以首先将连续坐标点映射成离散点.
映射可以将查询节点变得规范，不仅可以快速确定查询请求能否在缓存中命中路径，还可以识别同一批次中查询结果相同的查询请求，通过共享一个结果，减少查询次数.
为快速定位地理空间坐标点在G上的位置，本文采用KD-Tree索引映射二者之间的关系.与基于网格均匀划分区域空间的方式不同，KD-Tree将节点多的区域分割更加细致，节点少的区域分割更加粗糙.以此来提高映射的效率，为批量处理提供条件.
在获取应答Qs,t的候选路径集时，只需通过当前缓存中BMI的信息查询与源点vs和目标点vt相关的路径，即获得部分命中的候选路径集ц(vs)和ц(vt)，以及完全命中的候选路径集合ц(Ps,t).
3.3 最短路径评估模块
本模块用于评估从查询请求检测模块得到的候选路径集能否应答查询请求.本模块可以通过执行直接查询操作(direct query operation, DQO)，选择一条最优路径应答查询请求，或者通过执行连接查询操作(join query operation, JQO)获取一条连接路径用于应答查询请求.若2种操作皆无法获取应答查询请求的路径，则只能通过代理服务器获取最短路径.
直接查询操作DQO表示从ц(Ps,t)中选择一条距离当前时间最近的最短路径应答Qs,t.DQO可形式化为DQO(ц(Ps,t),T,Tmax)，满足：
(4)
连接查询操作JQO表示从ц(vs)及ц(vt)中各任选一条路径P∈ц(vs),P′∈ц(vt)来组成连接路径JPath(vs,vt)应答Qs,t.其中，JPath(vs,vt)需要满足时间约束Tmax以及欧氏距离约束EDR(vs,vm,vt).JQO形式化为JQO(vs,vt,θ,T,Tmax)，满足：
(5)
其中，JQO引入距离约束阈值θ，是因为连接路径JPath(vs,vt)的连接点vm可能偏离最短路径Ps,t，并出现在很远的位置，此时连接路径的旅行时间将变得不可靠.为避免连接路径的偏离，故设置欧氏距离比来控制vm的偏离程度，即：
EDR(vs,vm,vt)= 
(6)
表示从vs到vm和vm到vt的欧氏距离之和与vs到vt的欧氏距离比小于θ.θ的大小影响连接路径的旅行时间，θ越小连接路径的长度越趋近于最短路径，但当θ=1时并不一定是最短路径.
算法4展示了CTSPQ查询最短路径的伪代码.给定道路网G=(V,E,W,T)，首先初始化完全命中和部分命中的路径集合，并获取存储数据的AMPS信息(行①)，接着利用KD-Tree映射地理空间坐标vs(lat,lng)和vt(lat,lng)到G中的节点vs,vt上(行②)；在C中利用BMI信息获取vs和 vt所在的路径集，并作为应答查询请求的候选路径集(行③～④).若候选路径集中存在完全命中的路径，则根据式(4)获取最优路径返回到用户终端；否则根据式(5)获取一条连接路径，并返回结果(行⑤～).若DQO和JQO皆无法应答查询请求，则直接从代理服务器中获取精确的最短路径(行～).
算法4. 查询算法CTSPQ (C,Qs,t ,G,θ,Tmax).
输入：缓存C、查询请求Qs,t、道路网G、欧氏距离比θ、最大滞留时间Tmax；
输出：最短路径P.
① ц(vs),ц(vt)←空栈;P←空集;sign←
false;PII,ANI,BMI←从缓存C中
获取数据信息;
② vs,vt←KD-tree(Qs,t,G);
/*查询请求映射*/
③ ц(vs)← BMI(vs)；
/*获取vs所在的路径*/
④ ц(vt)←BMI(vt)；
/*获取vt所在的路径*/
⑤ if ц(vs)∩ц(vt)的路径集合不为空
⑥ P←DQO(vs,vt,T,Tmax);
/*见式(4)*/
⑦ return P； /*返回路径P*/
⑧ else
⑨ P←JQO(vs,vt,ц(vs),ц(vt),θ)；
/*见式(5)*/
⑩ if 存在连接路径P
return P；
end if
end if
P←getPath(Qs,t);
/*从服务器获取路径*/
return P.
以图3为例，在时刻T发出查询请求Q4,3，首先将Q4,3的源点和目标点映射到道路网子图G′上的节点v4和v3，然后在索引BMI中执行部分命中操作BMI(v4)={P1,4,P4,3,P2,7},BMI(v3)={P1,6,P1,5,P4,3}获取候选路径集ц(v3),ц(v4)和ц(P3,4)，在ц(P3,4)中存在路径P4,3满足|tP4,3-T|<Tmax，即满足DQO约束，故可以直接向用户端返回路径P4,3.
路径P4,3的旅行次序可以结合索引BMI和ANI中的数据获得.而获取旅行次序的过程与删除过程相似，继续以P4,3为例说明如何确定路径走向.令D记录已检索邻接点的节点，Z记录已访问但未检索邻接点的节点，第1步，通过random(P4,3)函数随机获取节点v6为P4,3检索起点，Z={v6}；第2步，根据ANI检索既在P4,3上又是v6邻接点的节点{v4,v5}，此时D={v6},Z={ v4,v5}.第3步，Z出栈v4，在P4,3上v4的邻接点集为{v6},v6∈D已被访问，且无其他邻接点，故可确定P4,3的一段子路径为〈v6→v4〉，此时D={v6,v4}、Z={v5}.同理，Z出栈v5，找到v5邻接点v3,v6，而v6∈D已被访问，得到P4,3的另一段子路径〈v6→v5→v3〉，此时D={v6,v4,v5}，Z={v3}.Z出栈v3，其在P4,3上的邻接点为{v5}，而v5∈D，Z=∅，已遍历上的P4,3所有节点，故通过检索起点v6连接2条子路径段可确定P4,3的旅行方向为〈v4→v6→v5→v3〉.
4 实验分析
本节通过在真实数据集上进行大量实验，验证了所提算法的有效性及可扩展性.
4.1 实验设置
本文实验环境见表2，采用的编程语言为Java.此外在相同的环境下，本文分别对SPC,EPC,Baseline,TSPC策略方法进行了对比测试.
Table 2 Experiment Environment
表2 实验环境
类别描述CPUIntel CoreTM i5-4200H CPU @ 2.80GHz内存∕GB12磁盘∕TB1WindowsMicrosoft Windows 10专业版 64位编译器gcc (tdm-1) 4.7.1
Fig. 6 Effect of cache size
图6 缓存大小的影响
4.2 数据集
本文使用的实验数据集来自文献[25]，利用加利福尼亚州道路网上的真实数据集进行实验.该网络具有真实的兴趣点，包含了21 693条边、21 048个节点和104 770个兴趣点.我们从兴趣点中随机选择2点作为测试的源点和目标点，用于生成时空路径进行实验，此外，测试部分的数据除了来自文献[25]之外，还有来自必应地图的实时查询数据.在实验过程中利用必应地图的API作为提供准确的最短旅行时间的服务器.在测试之前我们随机获取某一时刻的查询来预热缓存.
本文所涉及的实验若无特殊说明则代表缓存最多可容纳的节点数为50 000(每个节点占4 B)，缓存中所有数据的总容量不超过1 MB，同一时刻下的查询请求数量设为10 000，构建缓存的候选路径数量设为10 000，相似度阈值设为0.7，距离约束设为1.05. Tmax=15，缓存中路径滞留时间最大为15 min.
4.3 实验结果
4.3.1 映射
将地理坐标点映射到道路网G的过程中，本文采用了KD-Tree算法.KD-Tree划分的层级越多，映射结果越准确，为了更准确地识别数据，本文对道路网进行了精确的分割识别，在保证结果正确的前提下，可快速识别基于位置服务的点在G中的位置.图5描绘了Gird,KD-Tree,linear等方法在不同大小数据集下运行的时间.采用KD-Tree方法的映射速度明显优于Gird和linear方法.
Fig. 5 Response time of different mapping methods
图5 不同映射方法的响应时间
4.3.2 缓存大小
缓存容量的大小关乎整个系统的性能.缓存容量越小，命中率越低，但当缓存容量过大时，虽然命中率会明显提高，但会降低查询速度[31].
图6展示了不同缓存大小下SPC,EPC,Baseline,TSPC等算法的查询响应时间以及命中率，其中查询响应时间由映射过程时间以及在缓存中获取路径的时间组成.在图6(a)中，当缓存|C|>30 000时， 虽然EPC策略在缓存中的总耗时为TSPC,Baseline策略的10%～20%，但EPC在缓存中的命中率是TSPC和Baseline命中率的4%左右.综合分析，本文策略的整体效率较优.
在图6(b)中，随着缓存容量的增加，TSPC的命中率逐渐赶超Baseline的命中率.是因为受相似度的约束，TSPC缓存的节点种类比Baseline的多，可通过连接操作得到应答查询请求的路径.正因相似度约束，TSPC缓存的数据量并不会因为缓存容量的无限扩大而增加，缓存中的数据量会维持在一个范围内.
4.3.3 参数θ分析
由三角形三边关系可知，在连接操作中引入欧氏距离比阈值θ，意味着连接路径的长度不会被无线延伸，可避免偏差较大的候选路径.
图7显示了在不同θ下缓存的命中率及路径查询结果的准确度，θ的取值范围为[1.00，1.10].由图7(a)可知随着θ约束力度的放宽，以连接路径的形式应答查询请求的数量增多，命中率有较大的提升，但结果会出现较大的偏差.而在允许有10%的偏差下，TSPC和Baseline策略的命中率提升为90%以上，故在误差允许的范围内使用TSPC和Baseline可提高服务器的整体运行效率.
Fig. 7 Effect of θ
图7 θ值的影响
Fig. 8 Effect of τ
图8 τ值的影响
4.3.4 参数τ分析
图8显示了不同相似度阈值τ下的命中率以及准确率，τ值大小影响缓存中路径的多样性.当τ=0时，表示缓存中的数据集不存在相同节点，也就意味着当执行查询操作时，缓存路径只能进行完全命中操作，此时准确率达到最高；当τ=1时，缓存中的存储的路径不再受到相似度的约束，而是仅受到缓存容量的限制，即为Baseline操作.
如图8(a)所示，当τ∈[0.5,0.7]时，TSPC的缓存命中率远比未采用相似度约束的算法高，故相似度约束可明显改善小容量缓存的命中率.图8(b)～(c)显示了不同τ值下命中结果的准确率，虽然TSPC和Baseline策略在无误差情况下的准确率低于SPC的准确率，但是在τ=0.7时其命中率近似于SPC命中率的3倍，此外在容许存在10%误差的情况下，准确率达到90%以上.
5 总 结
针对时变道路网中在线查询最短路径效率慢的问题，本文利用缓存减少服务器的工作负载，首先为降低数据占用缓存空间，设计了一个缓存存储结构；其次，为实时地构建路径缓存提出了基于贪心策略和相似度约束的缓存存储策略，提高了缓存的命中率；最后根据存储结构中的索引特性，设计了一个利用缓存高效应答最短路径查询的算法.最终通过大量实验结果表明了本文所提的算法具有有效性和高效性.
作者贡献声明：黄阳负责实验及论文的起草；周旭、杨志邦提出算法优化方案，为共同通信作者；余婷、张吉负责索引设计及文字润色；曾源远、李肯立负责实验方案及论文整体架构设计.
[1]Ma Liantao, Wang Yasha, Peng Guangju, et al. Evaluation of GPS-environment friendliness of roads based on bus trajectory data[J]. Journal of Computer Research and Development, 2016, 53(12): 2694-2707 (in Chinese)(马连韬, 王亚沙, 彭广举, 等. 基于公交车轨迹数据的道路GPS环境友好性评估[J]. 计算机研究与发展, 2016, 53(12): 2694-2707)
[2]Liu Jianhua, Wang Xin, Shen Shigen, et al. Intelligent jamming defense using DNN stackelberg game in sensor edge cloud[J]. IEEE Internet of Things Journal, 2021. DOI: 10.1109/JIOT.2021.3103196
[3]Liu Jianhua, Shen Shigen, Yue Guangxue. A stochastic evolutionary coalition game model of secure and dependable virtual service in sensor-cloud[J]. Applied Soft Computing, 2015, 30: 123-135
[4]Li Lei, Hua Wen, Du Xingzhong, et al. Minimal on-road time route scheduling on time-dependent graphs[J]. Proceedings of the VLDB Endowment, 2017, 10(11): 1274-1285
[5]Akiba T, Iwata Y, Yoshida Y. Fast exact shortest-path distance queries on large networks by pruned landmark labeling[C] //Proc of the ACM SIGMOD Int Conf on Management of Data. New York: ACM, 2013: 349-360
[6]Li Lei, Zhang Mengxuan, Hua Wen, et al. Fast query decomposition for batch shortest path processing in road networks[C] //Proc of the 36th IEEE Int Conf on Data Engineering. Piscataway, NJ: IEEE, 2020: 1189-1200
[7]Li Xiaohua, Qiu Tao, Wang Ning, et al. Refreshment of the shortest path cache with change of single edge[J]. Expert Systems with Applications, 2017, 67: 1-11
[8]Li Xiaohua, Wang Bin, Qiu Tao, et al. Constructing effective caches of shortest path queries on road networks[J]. IEEE Access, 2020, 8: 193777-193789
[9]Zhang Detian, Liu An, Li Zhixu, et al. Effective shortest travel-time path caching and estimating for location-based services[J]. World Wide Web, 2019, 22(2): 455-475
[10]Yang Bin, Guo Chenjuan, Jensen C S, et al. Stochastic skyline route planning under time-varying uncertainty[C] //Proc of the 2014 IEEE 30th Int Conf on Data Engineering. Piscataway, NJ: IEEE, 2014: 136-147
[11]Greco S, Molinaro C, Pulice C. Efficient maintenance of shortest distances in dynamic graphs[J]. IEEE Transactions on Knowledge & Data Engineering, 2018, 30(3): 474-487
[12]Chang Lijun, Yu J X, Lu Qin, et al. The exact distance to destination in undirected world[J]. The VLDB Journal, 2012, 21(6): 869-888
[13]Zhu A D, Ma Hui, Xiao Xiaokui, et al. Shortest path and distance queries on road networks: Towards bridging theory and practice[C] //Proc of the ACM SIGMOD Int Conf on Management of Data. New York: ACM, 2013: 857-868
[14]Zhu A D, Xiao Xiaokui, Wang Sibo, et al. Efficient single-source shortest path and distance queries on large graphs[C] //Proc of the 19th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2013: 998-1006
[15]Cheng J, Ke Yiping, Chu Shumo, et al. Efficient processing of distance queries in large graphs: A vertex cover approach[C] //Proc of the ACM SIGMOD Int Conf Management of Data. New York: ACM, 2012: 457-468
[16]Zhang Xiaofei, Tamer O M. Correlation constraint shortest path over large multi-relation graphs[J]. Proceedings of the VLDB Endowment, 2019, 12(5): 488-501
[17]Wei V J, Wong C W, Long C. Architecture-intact oracle for fastest path and time queries on dynamic spatial networks[C] //Proc of the 2020 Int Conf on Management of Data. New York: ACM, 2020: 1841-1856
[18]Markatos E P. On caching search engine query results[J]. Computer Communications, 2001, 24(2):137-143
[19]Zhang Detian, Liu An, Jia Gangyong, et al. Effective caching of shortest travel-time paths for Web mapping mashup systems[J]. Web Information Systems Engineering, 2017, 10569: 422-437
[20]Thomsen J R, Yiu M L, Jensen C S. Effective caching of shortest paths for location-based services[C] //Proc of the ACM SIGMOD Int Conf on Management of Data. New York: ACM, 2012: 313-324
[21]Fagni T, Perego R, Silvestri F, et al. Boosting the performance of Web search engines: Caching and prefetching query results by exploiting historical usage data[J]. ACM Transactions on Information Systems, 2006, 24(1): 51-78
[22]Lai K M, Huang T W, Ho T Y. A general cache framework for efficient generation of timing critical paths[C] //Proc of the 56th Annual Design Automation Conf. New York: ACM, 2019: No.108
[23]Allulli L, Lichodzijewski P I, Zeh N R. A faster cache-oblivious shortest-path algorithm for undirected graphs with bounded edge lengths[C] //Proc of the 18th Annual ACM-SIAM Symp on Discrete Algorithms. New York: ACM, 2007: 910-919
[24]Zhang Y, Hsueh Y L, Lee W C, et al. Efficient cache-supported path planning on roads[J]. IEEE Transactions on Knowledge & Data Engineering, 2016, 28(4): 951-964
[25]Zhang Detian, Liu An, Jin Gaoming, et al. Edge-based shortest path caching for location-based services[C] //Proc of 2019 IEEE Int Conf on Web Services. Piscataway, NJ: IEEE, 2019: 320-327
[26]Albert Angel, Nick Koudas. Efficient diversity-aware search[C] //Proc of the ACM SIGMOD Int Conf on Management of Data. New York: ACM, 2011: 781-792
[27]Li Song, Dou Yanan, Hao Xiaohong, et al. The method of the K-dominant space skyline query in road network[J]. Journal of Computer Research and Development, 2020, 57(1): 227-239 (in Chinese)(李松, 窦雅男, 郝晓红, 等. 道路网环境下K-支配空间Skyline查询方法[J]. 计算机研究与发展, 2020, 57(1): 227-239)
[28]Deng Ting, Fan Wenfei. On the complexity of query result diversification[J]. Proceedings of the VLDB Endowment, 2013, 6(8): 577-588
[29]Qin Lu, Yu J X, Chang Lijun. Diversifying top-K results[J]. Proceedings of the VLDB Endowment, 2012, 5(11): 1124-1135
[30]Liu Huiping, Jin Cheqing, Yang Bin, et al. Finding top-k shortest paths with diversity[J]. IEEE Transactions on Knowledge and Data Engineering, 2018, 30(3): 488-502
[31]Wu Yu, Yang Juan, Liu Renping, et al. Survey on approximate storage techniques[J]. Journal of Computer Research and Development, 2018, 55(9): 2002-2015 (in Chinese)(吴宇, 杨涓, 刘人萍, 等. 近似存储技术综述[J]. 计算机研究与发展, 2018, 55(9): 2002-2015)
