时态图最短路径查询方法

张天明 徐一恒 蔡鑫伟 范 菁

1(浙江工业大学计算机科学与技术学院 杭州 310023) 2(浙江大学计算机科学与技术学院 杭州 310013)

图，作为一种通用的数据结构，用于表示各种对象之间的复杂关联关系.图上最短路径计算作为基础功能函数，有着广泛的应用.例如，路径规划、城市交通路线优化、社交网络分析等.现有的最短路径算法主要聚焦在普通图，然而，真实场景中，图中常常附有时态信息，2个顶点之间的边关联的事件在某一时间点发生并持续一段时间结束，此种类型的图称之为时态图.

Fig. 1 Illustration of bus timetable图1 公交时刻图示例

图1列举了时态图应用在公交时刻图的例子.图中顶点表示公交站点，时态边上附带有时态区间，表示公交车从一个站点到另一个站点的出发时间和到达时间.例如，一班89路公交车早上7∶00从浙大玉泉校区始发站出发，7∶15到达古荡站点，停靠站1 min，7∶16出发，经府苑新村，蒋村公交站，最终在8∶15到达三墩终点站.此例中，时态图最短路径查询有助于乘客查询指定时态区间内的2个站点间的最短路径，从而为乘客智能推荐公交线路.给定时态图

G

=(

V

,

E

)，查询源点

u

，查询目的点

v

，时态区间

I

，本文研究的时态图最短路径旨在图

G

中查询

u

到

v

在时态区间

I

内的最短时态路径距离

.

时态图

G

中的边除了关联时态区间外，还附加有权重值，在交通路网中可以表示距离；在公交

/

地铁

/

航班时刻图中可以表示费用；在社交网络中可以表示用户之间的亲密度

.

与已有的最短路径查询问题相比，最短时态路径更具挑战性

.

首先，计算最短时态路径时需要考虑边与边的时序流转特性，否则如果运用现有的普通图最短路径计算方法，会产生错误的结果.例如，图1中，假设边上权值均为1，乘客想要查询云栖小镇站到三墩站在时态区间[7∶00,9∶00]的时态最短路径距离.如果不考虑边之间的时序流转特性，则计算得到的结果为3，对应的最短时态路径为(云栖小镇，府苑新村，蒋村公交站，三墩)或(云栖小镇，府苑新村，董家村，三墩).实际这2条路径均不能到达三墩站.对于第一条路径，121路云栖小镇到府苑新村时间为8∶20，其不能赶上7∶32从府苑新村出发经由蒋村公交站最终到达三墩站的89路公交车.对于第二条路径，121路换乘70路8∶50到董家村，同样赶不上8∶26到三墩站的12专线.鉴于此，时态最短路径计算过程中需要考虑时序流转特性，此例计算得到的结果应为4，对应的最短时态路径应为(云栖小镇，翠苑，大关，董家村，三墩).

其次，最短时态路径并不满足子路径最优性质,即顶点

u

到顶点

v

的最短时态路径的子路径并不一定是最短时态路径.上例中，子路径(云栖小镇，翠苑，大关，董家村)并不是时态区间[7∶00,9∶00]内的最短时态路径，云栖小镇到董家村在时态区间[7∶00,9∶00]内最短时态路径应为(云栖小镇，府苑新村，董家村).这导致计算时态最短路径时更复杂，因为需要考虑所有的路径.

目前，已有一些工作研究时态图最短路径查询.然而，它们一般假设输入时态图为FIFO(first-in-first-out)时间依赖图，FIFO时间依赖图是指图输入边上的时间间隔表示为出发时间的函数，这个函数具有FIFO属性，即若出发时间早，则到达时间也早.这类问题具有一定的特殊性，实际交通工具出行时刻图或社交接触网络不一定是FIFO时间依赖图.与本文工作最相关的是文献[6-7]提出的one-pass算法，其将时态图转化为普通图，而后在普通图上采用广度优先搜索和Dijkstra算法计算最短时态路径，但其在较大规模数据集上效率较低.鉴于此，本文研究时态图最短路径问题并提出了基于层次索引的计算方法，其主要包含预处理和在线查询2个阶段.预处理阶段本文提出了一种无损压缩方法和层次索引CTG-tree(compressed transformed graph tree).首先将时态图转化为普通图，对普通图进行压缩以减小规模，将时态图上最短路径计算转化为在压缩结果图上执行.而后在压缩结果图上构建CTG-tree，它将G-tree的思想扩展到压缩有向图上，首先采用Metis划分将压缩图层次划分为若干个子图，得到每个子图的入边界点与出边界点集合.CTG-tree为每个叶子节点对应子图计算其内部顶点与出边界点的最短路径、入边界点到子图内顶点的最短路径和出边界点到入边界点的最短路径；非叶节点计算其对应子图入边界点到其所有孩子节点对应子图的入边界点之间的最短路径距离、所有孩子节点对应子图的出边界点到当前非叶节点对应子图的出边界点之间的最短路径距离、以及所有孩子节点对应子图的出边界点到所有孩子节点对应子图的入边界点之间的最短路径距离作为索引.查询阶段本文基于层次索引CTG-tree设计了高效的最短路径查询算法.概括而言，本文的主要贡献有4个方面:

1) 提出了一种基于层次索引的两阶段(预处理阶段和查询阶段)方法以高效地计算时态图最短路径;

2) 提出了一种无损压缩方法和层次索引CTG-tree，将时态图上最短路径计算结果转化为在压缩结果图上执行.CTG-tree将G-tree的思想扩展到压缩有向图上；无损压缩在减小图处理规模的同时还保证了压缩结果图上最短路径计算的准确性；

3) 提出了基于CTG-tree索引的查询算法以高效地支持时态图最短路径查询;

4) 基于4个真实的时态图数据集，进行了充分的实验评估，验证了本文提出的基于层次索引的最短时态路径算法的高效性.

1 相关工作

本节分别概述已有的普通图和时态图最短路径查询算法.

1.1 普通图最短路径查询算法

综述文献[1,9]将普通图最短路径问题划分为点到点的最短路径计算、单源最短路径计算和所有点对最短路径计算3类问题.点到点的最短路径计算指定点对之间的最短路径；单源最短路径计算一个点到其他所有点的最短路径距离；所有点对最短路径计算图中所有点对之间的最短路径距离,其可通过单源最短路径计算得到.已有的最短路径查询算法大多是基于经典的Dijkstra方法，文献[10]从理论角度分析了单源最短路径基于堆的优先级队列算法的时间复杂度是

O

(

m

log

n

)；采用斐波那契堆的时间复杂度是

O

(

m

+

n

log

n

).文献[11]提出了基于Dijkstra的变体方法Sky-Dijk.为了缩小搜索空间，双向搜索算法被提出.由于Dijkstra方法及其变体算法在大图上运行时间较长，因此研究人员提出了一系列基于索引的最短路径算法以提高查询效率.例如，文献[14]提出了基于标志点(landmark)的算法，其预先选择一些顶点作为标志点；并且预先计算图中每个顶点与标志点之间的最短路径距离.图中任意一对顶点之间的最短路径距离上下界可以运用预先计算好的距离计算得到；文献[15]提出了基于剪枝的标志点标签，通过剪枝的广度优先搜索预计算所有顶点的距离标签，通过距离标签计算任意点对的最短路径距离.文献[16]提出了收缩层级结构；将图中的顶点或者边按照重要度排序，再根据排序的结果迭代，最终生成层级嵌套索引.文献[8]提出了G-tree索引，其首先将路网层次划分为若干个子图，再计算每个子图内的顶点与边界点之间的距离，子图间的边界点与边界点之间的距离作为索引，基于G-tree索引提高查询效率.基于索引的最短路径算法关键在于平衡查询时间、索引时间、索引空间；为了减小索引空间，文献[17-18]还提出了索引压缩方法.针对动态图，文献[19]提出了DCHvcs,其扩展收缩层级结构以支持动态图.文献[20]在收缩层级最短路径索引的基础上，构建辅助的图结构以及权重传播机制来处理流式和批量的路网权重更新.文献[21]提出了CRP方法以支持最短路径索引的动态更新.针对大规模输入图，文献[22]基于分布式流处理系统Yahoo S4，提出了2种异步通信算法以支持动态最短路径；文献[23]探索了边受限的最短路径查询问题.此外，一些研究人员还致力于近似最短路径计算方法研究.文献[24]提出了距离Oracle数据结构，对于(2

k

-1)-近似能在

O

(

k

)的时间内给出任意节点对之间的近似最短路径.文献[25]将大图近似为一个规模相对小的spanner稀疏子图，而后在子图上做近似最短路径计算.概括而言，上述算法均针对普通图，并没有考虑边上附带的时态信息，因此不能直接有效地应用在时态图上.

1.2 时态图最短路径查询算法

综述文献[1]总结了时间依赖图的最短路径查询算法.时间依赖图中边延迟函数计算一条边中源点到目的点所需时间，时间函数可分为离散或连续的.

文献[2,6-7,26]针对离散时间下的最短路径进行了研究.文献[2]提出了TD-G-tree索引以支持时间依赖路网上最短路径查询，但是其与本文研究问题不同，并没有考虑路径内边之间的时序关系.文献[26]提出了时间表标签(time table labelling, TTL)索引；文献[6-7,27]提出将时态图转化为普通图，基于此，文献[27]研究了时间依赖的可达性查询，其提出了TopChain标签索引方法以解决时态图上的可达性查询、最早到达时间查询、最小间隔时间查询.与其研究的问题不同，本文旨在解决时态图上的最短路径查询.文献[6-7]在转化的普通图上采用广度优先搜索和Dijkstra算法计算2点之间给定时间段内的最短路径.本文基于上述工作，将时态图转化为普通图后，利用压缩以及层次索引技术高效支持最短时态路径查询.

文献[3-5]针对连续时间下的最短路径进行了研究.文献[4]提出了基于Dijkstra算法返回耗时最少旅行时间的最优出发时间；文献[3]首先定位给定时态区间段内子图，而后在子图中采用Dijkstra计算最短路径.文献[5]在文献[4]的基础上，研究的时态图中边除了边延迟函数外，还添加了权重代价函数，利用这2种函数的结构属性设计最短路径算法.这类工作通常假设输入时态图为FIFO时间依赖图，输入边上时间间隔表示为出发时间的函数，出发时间早，则到达时间也早，这类问题具有一定的特殊性.而在我们的问题中，输入边有出发时间和到达时间，输入图(例如交通工具出行时刻图或者社交接触网络)不一定是FIFO时间依赖图，这导致计算时态最短路径时更复杂，最短路径计算不满足最优子结构特征，因为需要考虑边与边的时序流转特性，计算难度更高.

2 问题定义

本节主要介绍时态图、时态路径相关概念，最后给出问题定义.

定义1.

时态图

.

本文定义的时态图是复杂有向图，表示为

G

=(

V

,

E

)，其中

V

表示顶点集合；

E

⊆

V

×

V

是有向边的集合，具体地，连接顶点

u

∈

V

到

v

∈

V

/

{

u

}的有向边

e

∈

E

表示为一个五元组(

u

,

v

,

w

,

s

,

a

)，表示

u

与

v

之间的事件发生起始时间是

s

，终止时间是

a

.

时间间隔是

I

=(

s

,

a

)，持续时间为|

I

|=

a

-

s

，

w

表示每条时态边

e

的非负权重值，表示耗费时间或者路程等

.

不同于简单图，时态图中2个顶点之间可能有多条时态边

.

与普通图路径定义不同，时态图中时态路径的定义如下：

给定时态图

G

，源点

s

，目的点

s

′，时间间隔

I

=[

t

,

t

]，定义函数

TPSet

(

s

,

s

′,

I

=[

t

,

t

])为从顶点

s

到顶点

s

′的所有满足

S

≥

t

,

E

≤

t

的

G

中的时态路径

p

构成的集合

.

基于此给出定义3

.

3 CTG-Tree构建

本文提出了基于层次索引的计算方法，主要包含预处理和在线查询2个阶段.本节详细阐述预处理阶段提出的无损压缩方法和层次索引CTG-tree.

3.1 基于转化图的无损压缩

在时态图上计算最短时态路径的直接方法是进行广度优先搜索或者深度优先搜索，但是由于时态最短路径不满足子路径最优性质，因此在搜索过程中需要保存计算遍历到的所有路径，此种方法效率较低.因此本文的主要思想是先将时态图转化为普通图，而后进行压缩，再利用索引加速查询.具体地，本文利用文献[6]提出的方法将时态图

G

=(

V

,

E

)转化为普通图

G

=(

V

,

E

)，其中转化图

G

已被证明为有向无环图，具体的转化过程如下

.

Fig. 2 Illustrations of temporal graph,transformed graph, and compressed graph图2 时态图、转化图和压缩图示例

算法1.

基于转化图的无损压缩算法

.

输入：基于时态图

G

=(

V

,

E

)的转化图

G

=(

V

,

E

)；输出：无损压缩图

G

′=(

V

′,

E

′)

.

/

*根据规则进行压缩*

/

④ end if

⑤ end for

⑥ 输出无损压缩图

G

′=(

V

′,

E

′)

.

3.2 CTG-tree索引

基于上述无损压缩图，构建层次索引CTG-tree.分为2个步骤：

1)
图层次划分.由于Metis划分保证每次划分的子图顶点数目相近，交叉边数目较少，因此本文采用Metis层次划分，首先将无损压缩图

G

′划分为若干子图

G

，

G

，…，

G

(

l

≥2)，而后在每个子图

G

(1≤

i

≤

l

)上进行迭代划分直至划分的子图顶点数目不超过指定的阈值

θ

；最终形成平衡树CTG-tree

.G

′为CTG-tree的根节点，第

i

次迭代划分的子图为CTG-tree第

i

层节点，叶子节点对应子图的顶点数目不超过阈值

θ.

Metis划分属于边划分方法，每次迭代划分的子图之间没有交集(例

G

∪

G

∪…∪

G

=

G

′,

G

∩

G

∩…∩

G

=∅)，但是会产生跨子图的交叉边

e

(

u

,

v

),

u

∈

G

,

v

∈

G

.

基于此，本文将子图内顶点分为3类：入边界点、出边界点和内部顶点

.

令

G

.B

,

G

.B

,

G

.V

分别表示子图

G

=(

V

,

E

)的入边界点、出边界点和内部顶点的集合，则①

V

=

G

.B

∪

G

.B

∪

G

.V

；② ∀

u

∈

G

.B

，至少存在一条跨分区的交叉边

e

=(

u

,

m

),

u

与

m

隶属不同子图，即

m

∉

G

；③ ∀

v

∈

G

.B

，至少存在一条跨分区的交叉边

e

=(

s

,

v

),

s

与

v

隶属不同子图，即

s

∉

G

；④ ∀

v

′∈

G

.V

，

v

′的所有入度邻居

.

出度邻居都隶属子图

G

，即

N

(

v

′)⊆

V

,

N

(

v

′)⊆

V

；在图划分步骤中，每个子图记录相应的入边界点，出边界点

.

2) 最短路径距离矩阵计算

.

对于CTG-tree中的叶子节点对应的子图

G

，需要计算3个最短路径距离矩阵，即游出距离矩阵

G

.

、游入距离矩阵

G

.

和边界点距离矩阵

G

.

.

G

.

保存

G

中所有顶点到每个出边界点的最短路径距离；

G

.

保存

G

中每个入边界点到所有顶点的最短路径距离；

G

.

保存

G

中所有出边界点到入边界点的最短路径距离

.

对于CTG-tree中的非叶子节点对应的子图

G

，需要计算出边界点游入距离矩阵

G

.

、入边界点游入距离矩阵

G

.

和边界点游出距离矩阵

G

.

；

G

.

保存

G

所有孩子节点对应子图的出边界点到

G

所有孩子节点对应子图的入边界点之间的最短路径距离；

G

.

保存

G

入边界点到

G

所有孩子节点对应子图的入边界点之间的最短路径距离；

G

.

保存

G

所有孩子节点对应子图的出边界点到

G

出边界点之间的最短路径距离

.

具体的CTG-tree索引构建算法伪码如算法2所示

.

算法2.

CTG-tree索引构建算法

.

输入：无损压缩图

G

′=(

V

′,

E

′)，Metis每层划分的子图数

l

，叶子子图顶点数阈值

θ

；

输出：CTG-tree索引.

① CTG-tree←

Metis

(

G

′,

l

,

θ

)；

② for each layer(自底向上) of CTG-tree

③ if leaf node←

/

*叶子节点层计算*

/

④

G

.

,

G

.

,

G

.

←

Dijkstra

(

G

′)；⑤ else

/

*非叶子节点层计算*

/

⑥

G

.

←

Dijkstra

(

G

′);

G

.

←

Dijkstra

(

G

′);

G

.

←

Dijkstra

(

G

′)；

⑦ end if

⑧ end for

⑨ 输出CTG-tree索引.

算法2首先在给定的无损压缩图

G

′上进行Metis层次划分，得到CTG-tree(行①)，需要说明的是，无损压缩图中，边权重为0会影响Metis划分过程，因此需要适当增权处理.接着，对CTG-tree自底向上遍历计算索引矩阵(行②).对于叶子节点，利用Dijkstra算法在图

G

′上计算叶子节点对应子图

G

的游出距离矩阵

G

.

、游入距离矩阵

G

.

和边界点距离矩阵

G

.

(行③～④)

.

对于非叶节点，利用Dijkstra算法在图

G

′上计算对应子图

G

的出边界点游入距离矩阵

G

.

、边界点游出距离矩阵

G

.

和入边界点游入距离矩阵

G

.

，值得注意的是，此过程可以利用顶点拓扑序加速计算过程，由于转化图是有向无环图，压缩图即为有向无环图，因此在运用Dijkstra算法前，可先计算顶点拓扑序，若在计算顶点

u

到

v

的最短路径时，

u

的拓扑序大于

v

的拓扑序，则顶点

u

到

v

的最短路径一定为∞

.

Fig. 3 Metis Partitioning and CTG-tree Construction图3 Metis划分以及CTG-tree构建过程

随后，计算CTG-tree中的叶子节点对应子图

G

，

G

，

G

和

G

的游出距离矩阵

G

.

、游入距离矩阵

G

.

和边界点距离矩阵

G

.

.

而后，自底向上计算非叶节点对应子图

G

，

G

和

G

的出边界点游入距离矩阵

G

.

、入边界点游入距离矩阵

G

.

和边界点游出距离矩阵

G

.

.

Fig.4 Distance Matrix Index in CTG-tree图4 CTG-tree中的距离矩阵索引

CTG-tree索引保存3部分信息：CTG-tree节点、边界点以及距离矩阵.CTG-tree叶子节点对应子图的顶点数目不超过阈值

θ

,每层节点数为

l

，所以CTG-tree高度为log(|

V

|

/θ

)+1，CTG-tree节点总数为

l

|

V

|

/

(

l

-1)

θ.

CTG-tree边界点总数为

CTG-tree距离矩阵大小为

所以CTG-tree索引空间复杂度为

4 基于CTG-tree索引的最短路径计算方法

本节详细阐述在线查询阶段提出的基于层次索引CTG-tree的最短路径计算方法.

具体的基于

G

′构建的CTG-tree索引的最短路径查询算法伪码如算法3所示

.

算法3.

最短路径查询算法

CTGQ

(

T

,

s

,

s

′,

I

=[

t

,

t

])

.

输入：基于

G

′构建的CTG-tree索引

T

，查询源点

s

，目的点

s

′，时间间隔

I

=[

t

,

t

]；输出：

s

在时间间隔

I

内到达

s

′的最短时态路径距离

.

⑦ end if

，

其中

5 实验分析

本节在真实的数据集上对所提出的CTGQ方法进行实验测试，并与2种流行方法1-pass和TDFS进行对比，以验证CTGQ的效率.

5.1 实验设置

本文使用4个真实数据集进行实验测试，分别是GTFS数据集Transit，以及SNAP公开的数据集Bitcoin，Mathoverflow，Askubuntu.Transit数据集记录了美国科罗拉多州丹佛县班车数据，包括班车号、班车出发时间、到达时间，停靠站点等信息.Bitcoin数据集是一个who-trust-whom网络，网络中的顶点表示在一个名为比特币OTC交易平台上使用比特币进行交易的用户；由于比特币用户是匿名的，为防止欺诈和风险用户交易，用户之间会进行声誉评分，因此网络中的边记录一个用户给另一个用户的声誉评分以及评分时间.Mathoverflow和Askubuntu数据集均为Stack Exchange下的互动时态网络，顶点表示用户，从用户

u

到用户

v

的边包含3种类型的互动关系:用户

u

在时间

t

回答了

v

的问题；用户

u

在时间

t

评论了

v

的问题；用户

u

在时间

t

评论了

v

的回答

.

表1给出了实验测试中用到数据集的统计信息

.

其中|

V

|,|

E

|,|

T

(

G

)|分别表示时态图的顶点数、边数和时态区间数

.

对于每个数据集，随机选取500组查询，查询时间间隔默认为

I

=[0,+∞],报道每个算法的平均查询时间

.

Table 1 Statistics of the Datasets表1 数据集统计信息

本文将CTGQ与1-pass和TDFS进行对比.1-pass算法和和TDFS均无需构建索引，1-pass算法在转化图上运用Dijkstra算法计算最短时态路径；TDFS算法在原始时态图上进行深度优先遍历计算最短时态路径；实验测试过程中，为取得较好的索引性能和查询性能，4个数据集Transit，Bitcoin，Mathoverflow，Askubuntu默认参数

l

=16;

θ

分别设置为128，64，256，128.本文所有实验程序均使用C++语言编写，实验测试环境为一台配置为英特尔至强CPU处理器E5-2650 v4，128 GB内存，1 TB硬盘的服务器.

5.2 实验结果与分析

表2给出了原始数据集采用3.1节提出的规则进行转化和压缩后得到的转化图和压缩图的大小.与表1数据进行对比，可以看出转化图的顶点数是原始图顶点数的4～97倍，转化图的边数是原始图边数的2～4倍.相较于转化图，压缩图顶点数是转化图顶点的3～50倍，压缩图边数是转化图边数的2～3倍，说明了本文提出压缩规则的有效性.

Table 2 Statistics of the Transformed Graph and the Compressed Graph

Fig. 5 Effect of Time Interval图5 时间区间的影响

表3给出了CTG-tree索引构建时间和空间代价.可以看出，Transit数据集上构建CTG-Tree索引需要时间不足1 s；Askubuntu数据集上构建CTG-tree索引需要时间接近8 min.在4个真实数据集上，CTG-tree索引大小在20 MB到8.2 GB之间.

Table 3 CTG-tree Construction Cost and Space Overhead表3 CTG-tree索引构建时间和空间代价

表4给出了CTGQ,1-pass和TDFS算法在4个数据集上的平均查询时间.由表4可以观察出，CTGQ查询时间比1-pass平均快1个数量级，比TDFS平均快2个数量级.这是因为1-pass算法与TDFS算法均需要在线遍历搜索，1-pass算法需要在转化图上运用Dijkstra算法计算2点之间的最短时态路径;TDFS算法在计算最短时态路径时，由于最短时态路径的子路径不满足最优子结构性质，所以TDFS需要遍历的时态路径是指数级的，耗时更长；而CTGQ利用了CTG-tree索引进行查询，查询过程中无需再遍历压缩图，只需要根据CTG-tree索引矩阵即可得到结果，因此效率更高.

Table 4 Query Time表4 查询时间 ms

本文实验验证了4个不同的时间间隔

I

(1≤

i

≤4)对最短时态路径查询时间的影响

.I

是数据集的最大时间间隔，

I

+1(1≤

i

≤3)是将

I

划分为2个相等子区间后的第一个子区间.图5给出了CTGQ,1-pass和TDFS算法在Transit，Bitcoin，Mathoverflow，Askubuntu数据集上的实验结果.

从图5可以看到，CTGQ，1-pass和TDFS的查询时间随着时态区间的缩减而降低，TDFS下降趋势最为显著.这是因为时态区间缩减时，TDFS所需遍历的时态路径数目大幅度减少；而1-pass和CTGQ算法在压缩图上计算，时态区间减小时，1-pass算法遍历的路径长度减小，CTGQ算法遍历的CTG-tree矩阵索引计算量减少.

另外，从图5还可以观察到不同查询时态区间下，CTGQ算法的性能始终远远优于1-pass和TDFS算法的性能，这与前述实验分析结论一致.

本文考察了叶子子图顶点数目阈值

θ

、迭代划分子图数目

l

对CTG-tree构建和CTGQ算法运行性能的影响.表5给出了4个数据集Transit，Bitcoin，Mathoverflow，Askubuntu在

θ

值分别设置为2，4，8，16，

l

值分别设置为32，64，128，256，512情况下的CTG-tree索引构建时间和CTGQ算法运行时间结果.

Table 5 Effects of θ and l表5 θ和l的影响 ms

首先由表5可以看到，当

l

取固定值时，CTG-tree索引构建时间随着

θ

值增加呈减少趋势

.

这是因为

θ

值增加，CTG-tree叶子节点对应子图的顶点数目增多，迭代划分产生的总子图数目减少，相应的入边界点、出边界点总数减少，索引矩阵计算量减少，因此CTG-tree索引构建时间降低.其次，由表5可以看出，当

θ

取固定值时，CTG-tree索引构建时间随着

l

值增大基本呈先降低再升高的趋势

.

这是因为随着

l

值的增大，CTG-tree每层节点数目增多，入边界点、出边界点总数先减少再增多，导致索引矩阵计算量先减小后增加.此外，当

θ

取固定值时，CTGQ算法运行时间随着

l

值增大基本呈降低趋势

.

这是因为，

l

值增大，CTG-tree高度降低，CTGQ算法自底向上，自顶向下遍历层数减少.鉴于上述观察，为取得较好的索引性能和查询性能，4个数据集默认参数

l

=16;

θ

在数据集Transit，Bitcoin，Mathoverflow，Askubuntu上的值分别设置为128，64，256，128.

6 总 结

本文研究了时态图最短路径问题并提出了基于CTG-tree索引的计算方法，其主要包含预处理阶段和在线查询阶段.在预处理阶段，本文提出了一种无损压缩方法和层次索引CTG-tree.其首先将时态图转化为普通图，对普通图进行无损压缩以减小图处理规模，将时态图上最短路径计算转化为在压缩图上执行；而后对压缩图采用Metis划分将压缩图层次划分为若干个子图，得到每个子图的入边界点与出边界点集合，并基于此构建CTG-tree.CTG-tree为每个叶子节点对应子图计算游入距离矩阵、游出距离矩阵和边界点距离矩阵；为每个非叶节点对应子图计算出边界点游入距离矩阵，入边界点游入距离矩阵和边界点游出距离矩阵.查询阶段本文基于CTG-tree索引设计了高效的最短路径查询算法.最后，在真实的时态图数据集上进行了全面的实验，实验结果验证了本文所提出的基于CTG-tree索引的算法的效率.此外，设计高效的分布式时态图最短路径方法与增量计算算法也是一个重要且值得研究的问题，后续工作计划对其进行深入地探索.

作者贡献声明

：张天明负责问题定义、方法设计、数据分析与论文撰写修改工作；徐一恒负责数据收集与整理、实验结果可视化工作；蔡鑫伟负责部分实验测试和整理工作；范菁负责指导论文写作并提出修改建议.