Temporal shortest path counting query algorithm based on tree decomposition

doi:10.11772/j.issn.1001-9081.2023081128

Journal of Computer Applications ›› 2024, Vol. 44 ›› Issue (8): 2446-2454.DOI: 10.11772/j.issn.1001-9081.2023081128

• Data science and technology • Previous Articles

Temporal shortest path counting query algorithm based on tree decomposition

Yuan LI¹, Qiulan LIN¹, Anzhi CHEN¹, Guoli YANG²(), Wei SONG¹, Guoren WANG³

^1.School of Information Science and Technology，North China University of Technology，Beijing 100144，China
^2.Advanced Institute of Big Data （Beijing），Beijing 100195，China
^3.School of Computer Science and Technology，Beijing Institute of Technology，Beijing 100081，China

Received:2023-08-23 Revised:2023-11-08 Accepted:2023-11-16 Online:2024-08-22 Published:2024-08-10
Contact: Guoli YANG
About author:LI Yuan， born in 1986， Ph. D.， associate professor. His researchinterests include data mining， database， bioinformatics.
LIN Qiulan ， born in 1998， M. S. candidate. Her research interestsinclude graph data management and mining.
CHEN Anzhi， born in 2001. His research interests include graphdata management and mining.
YANG Guoli， born in 1987， Ph. D.， associate research fellow. Hisresearch interests include data management， data mining；
SONG Wei ， born in 1980， Ph. D.， professor. His researchinterests include data mining.
WANG Guoren， born in 1966， Ph. D.， professor. His researchinterests include XML data mining， query processing and optimization，bioinformatics.
Supported by:
This work is partially supported by National Natural ScienceFoundation of China（ 61902004， 72201275， 61977001）.

基于树分解的时序最短路径计数查询算法

李源¹, 林秋兰¹, 陈安之¹, 杨国利²(), 宋威¹, 王国仁³

^1.北方工业大学信息学院, 北京 100144
^2.北京大数据先进技术研究院, 北京 100195
^3.北京理工大学计算机学院, 北京 100081

通讯作者: 杨国利
作者简介:李源（1986—），男，北京人，副教授，博士，CCF会员，主要研究方向：数据挖掘、数据库、生物信息学
林秋兰（1998—），女，广西贺州人，硕士研究生，主要研究方向：图数据管理与挖掘
陈安之（2001—），男，北京人，主要研究方向：图数据管理与挖掘
杨国利（1987—），男，北京人，副研究员，博士，主要研究方向：数据管理、数据挖掘 yanggl@aibd.ac.cn
宋威（1980—），男，北京人，教授，博士，CCF会员，主要研究方向：数据挖掘
王国仁（1966—），男，北京人，教授，博士，CCF杰出会员，主要研究方向：XML数据挖掘、查询处理和优化、生物信息学。
基金资助:
国家自然科学基金资助项目(61902004)

Abstract

Abstract:

The shortest path counting is an important research problem in graph computing. It aims to query the number of shortest paths between vertices， which is widely used in path planning and recommendation， social network analysis， betweenness centrality calculation and so on. At present， more and more networks can be modeled as temporal graphs， but there is no research work on the shortest path counting query problem of temporal graphs. Compared with the static graph， the temporal graph increases the time information， the structure is more complex， and the activation time of the edge must be considered when querying the number of paths between vertices. Therefore， the shortest path counting method for the static graphs is no longer applicable to the temporal graphs， and querying on large-scale temporal graphs is more challenging. In order to solve the shortest path counting problem of temporal graphs， a method of TG-TL （Temporal Graph-Tree Label） index based on tree decomposition was proposed. The method consists of two stages： index construction and online query. In the index construction stage， the temporal tree decomposition algorithm was designed according to the attributes of the temporal graph， and the temporal graph was transformed into a tree structure. Then， according to the structure information of tree decomposition and convex path definition， an efficient index building algorithm was proposed. In the online query stage， an efficient temporal shortest path counting query algorithm was proposed based on TG-TL index. Experiments were carried out on 4 real datasets， and the experimental results showed that compared with the query algorithm based on TG-base （Temporal Graph-base） index， the proposed algorithm improved the query efficiency by 61% at least. Therefore， the proposed algorithm is efficient and effective for the shortest path counting problem of temporal graphs.

Key words: temporal graph, tree decomposition, index, shortest path, shortest path counting

摘要：

最短路径计数是图计算中的一个重要研究问题，旨在查询顶点间的最短路径数，在路径规划与推荐、社交网络分析、介数中心性计算等领域中具有广泛应用。目前越来越多的网络可以建模为时序图，但少有针对时序图最短路径计数查询问题的研究工作。与静态图相比，时序图增加了时间信息，结构更复杂，在查询顶点间的路径数时必须考虑边的激活时间，因此静态图中最短路径计数方法不再适用于时序图，并且在大规模时序图上查询更具有挑战性。针对时序图最短路径计数问题，提出一种基于树分解构建TG-TL（Temporal Graph-Tree Label）索引的方法。该方法包含构建索引和在线查询两个阶段，构建索引阶段根据时序图的属性设计时序树分解算法，将时序图转化为树结构；然后根据树分解的结构信息以及凸路径定义提出高效构建索引算法；在线查询阶段基于TG-TL索引提出了高效的时序最短路径计数查询算法。在4个真实数据集上的实验结果表明，与基于TG-base（Temporal Graph-base）索引的查询算法相比，所提算法在查询效率上至少提升了61％，因此所提算法在时序图最短路径计数问题上具有高效性和有效性。

关键词: 时序图, 树分解, 索引, 最短路径, 最短路径计数

CLC Number:

TP311.1

Yuan LI, Qiulan LIN, Anzhi CHEN, Guoli YANG, Wei SONG, Guoren WANG. Temporal shortest path counting query algorithm based on tree decomposition[J]. Journal of Computer Applications, 2024, 44(8): 2446-2454.

李源, 林秋兰, 陈安之, 杨国利, 宋威, 王国仁. 基于树分解的时序最短路径计数查询算法[J]. 《计算机应用》唯一官方网站, 2024, 44(8): 2446-2454.

Figures/Tables 7

Fig.1 Temporal graph Gt

Fig. 2 Temporal tree decomposition TGt?of temporal graph Gt

Tab. 1 Statistics of experiment datasets

数据集	节点数	边数	数据集	节点数	边数
alpha	3 783	24 186	math	21 688	107 581
otc	5 881	35 592	ask	137 517	280 102

Fig. 3 Comparison of index construction time and size between TG-TL and TL-base

Tab. 2 Query time comparison between TG-TL and TL-base

数据集	TG-TL	TG-base	数据集	TG-TL	TG-base
alpha	42	107	math	105	273
otc	61	171	ask	198	565

Fig. 4 Comparison of visited labels in query processing between TG-TL and TL-base

Fig. 5 Comparison of influence of query time interval on query efficiency between TG-TL and TL-base

References 29

1	WU H， CHENG J， KE Y， et al. Efficient algorithms for temporal path computation［J］. IEEE Transactions on Knowledge and Data Engineering， 2016， 28（11）： 2927-2942.
2	王一舒，袁野，刘萌，等.大规模时序图数据的查询处理与挖掘技术综述［J］.计算机研究与发展，2018，55（9）：1889-1902.
	WANG Y S， YUAN Y， LIU M， et al. Survey of query processing and mining techniques over large temporal graph database［J］. Journal of Computer Research and Development，2018，55（9）：1889-1902.
3	ZHANG J， LI W， YUAN L， et al. Shortest-path queries on complex networks： experiments， analyses， and improvement［J］. Proceedings of the VLDB Endowment， 2022， 15（11）： 2640-2652.
4	ZHANG S， CUI X， CHENG Y， et al. Online global query planning for dynamic road networks［C］// Proceedings of the 2022 IEEE 8th International Conference on Cloud Computing and Intelligent Systems. Piscataway： IEEE， 2022： 666-670.
5	LATAPY M， VIARD T， MAGNIEN C. Stream graphs and link streams for the modeling of interactions over time［J］. Social Network Analysis and Mining， 2018， 8： No. 61.
6	WANG Y， YUAN Y， ZHANG W， et al. Reachability-driven influence maximization in time-dependent road-social networks［C］// Proceedings of the 2022 IEEE 38th International Conference on Data Engineering. Piscataway： IEEE， 2022： 367-379.
7	ZHANG Y， YU J X. Hub labeling for shortest path counting［C］// Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data. New York： ACM， 2020： 1813-1828.
8	QIU Y-X， WEN D， QIN L， et al. Efficient shortest path counting on large road networks［J］. Proceedings of the VLDB Endowment， 2022， 15（10）： 2098-2110.
9	PENG Y， YU J X， WANG S. PSPC： efficient parallel shortest path counting on large-scale graphs［C］// Proceedings of the 2023 IEEE 39th International Conference on Data Engineering. Piscataway： IEEE， 2023： 896-908.
10	WU H， CHENG J， HUANG S， et al. Path problems in temporal graphs［J］. Proceedings of the VLDB Endowment， 2014， 7（9）：721-732.
11	李新玲，王一舒，袁野，等. TD-H2H：时序图上的最短路径查询［J］. 计算机科学与探索， 2023， 17（5）： 1210-1224.
	LI X L， WANG Y S， YUAN Y， et al. TD-H2H： shortest path query on time-dependent graphs［J］. Journal of Frontiers of Computer Science and Technology，2023，17（5）：1210-1224.
12	YUAN Y， LIAN X， WANG G， et al. Constrained shortest path query in a large time-dependent graph［J］. Proceedings of the VLDB Endowment， 2019， 12（10）： 1058-1070.
13	KAUFMAN D E， SMITH R L. Fastest paths in time-dependent networks for intelligent vehicle-highway systems application［J］. Journal of Intelligent Transportation Systems： Technology， Planning， and Operations， 1993， 1（1）： 1-11.
14	HALIN R. S-functions for graphs［J］. Journal of Geometry， 1976， 8： 171-186.
15	WEI-KLEINER F. Tree decomposition-based indexing for efficient shortest path and nearest neighbors query answering on graphs［J］. Journal of Computer and System Sciences， 2016， 82（1）： 23-44.
16	DIJKSTRA E W. A note on two problems in connexion with graphs［M］// Edsger Wybe Dijkstra： His Life， Work， and Legacy. New York： ACM， 2022： 287-290.
17	FLOYD R W. Algorithm 97： shortest path［J］. Communications of the ACM， 1962， 5（6）： 345.
18	CHEN Z， FU A W-C， JIANG M， et al. P2H： efficient distance querying on road networks by projected vertex separators［C］// Proceedings of the 2021 International Conference on Management of Data. New York： ACM， 2021： 313-325.
19	OUYANG D， QIN L， CHANG L， et al. When hierarchy meets 2-hop-labeling： efficient shortest distance queries on road networks［C］// Proceedings of the 2018 International Conference on Management of Data. New York： ACM， 2018： 709-724.
20	XU Q， ZHANG X， ZHAO J， et al. Fast shortest-path queries on large-scale graphs［C］// Proceedings of the 2016 IEEE 24th International Conference on Network Protocols. Piscataway：IEEE， 2016： 1-10.
21	ZHENG B， WAN J， GAO Y， et al. Workload-aware shortest path distance querying in road networks［C］// Proceedings of the 2022 IEEE 38th International Conference on Data Engineering. Piscataway：IEEE， 2022： 2372-2384.
22	KANOULAS E， DU Y， XIA T， et al. Finding fastest paths on a road network with speed patterns［C］// Proceedings of the 22nd International Conference on Data Engineering. Piscataway： IEEE， 2006： 10.
23	BATZ G V， DELLING D， SANDERS P， et al. Time-dependent contraction hierarchies［C］// Proceedings of the 11th Workshop on Algorithm Engineering and Experiment. Philadelphia： Society for Industrial and Applied Mathematics， 2009： 97-105.
24	DING B， YU J X， QIN L. Finding time-dependent shortest paths over large graphs［C］// Proceedings of the 11th International Conference on Extending Database Technology： Advances in Database Technology. New York： ACM， 2008： 205-216.
25	DELLING D， WAGNER D. Time-dependent route planning［M］// Robust and Online Large-Scale Optimization： Models and Techniques for Transportation Systems. Berlin： Springer， 2009： 207-230.
26	张天明，徐一恒，蔡鑫伟，等.时态图最短路径查询方法［J］.计算机研究与发展， 2022， 59（2）： 362-375.
	ZHANG T M， XU Y H， CAI X W， et al. A shortest path query method over temporal graphs［J］. Journal of Computer Research and Development， 2022， 59（2）： 362-375.
27	DEMIRYUREK U， BANAEI-KASHANI F， SHAHABI C， et al. Online computation of fastest path in time-dependent spatial networks［C］// Proceedings of the 12th International Conference on Advances in Spatial and Temporal Databases. Berlin： Springer， 2011： 92-111.
28	WANG Y， LI G， TANG N. Querying shortest paths on time dependent road networks［J］. Proceedings of the VLDB Endowment， 2019， 12（11）： 1249-1261.
29	ABSEHER M， MUSLIU N， WOLTRAN S. Improving the efficiency of dynamic programming on tree decompositions via machine learning［J］. Journal of Artificial Intelligence Research， 2017， 58（1）： 829-858.

[1]	Fanjun MENG, Bin HAN, Shucheng HUANG, Xiangdong MEI. Distributed temporal index for temporal aggregation range query [J]. Journal of Computer Applications, 2024, 44(6): 1848-1854.
[2]	Chuanyu ZONG, Chunhe ZHANG, Xiufeng XIA. Maximum cycle truss community search based on hierarchical tree index on directed graphs [J]. Journal of Computer Applications, 2024, 44(1): 190-198.
[3]	Xiaoyu ZHANG, Ziqiang YU, Chengdong LIU, Bohan LI, Changfeng JING. Spatial-temporal co-occurrence pattern mining algorithm for video data [J]. Journal of Computer Applications, 2023, 43(8): 2330-2337.
[4]	Ting YANG, Ruoyu MO, Xiujuan ZHANG, Zhousen ZHU. Enhancement and expansion of full-text search in relational databases based on lightweight caching strategy [J]. Journal of Computer Applications, 2023, 43(8): 2431-2438.
[5]	Hua JIANG, Xing LI, Huijiao WANG, Jinghai WEI. Cross-level high utility itemsets mining algorithm based on data index structure [J]. Journal of Computer Applications, 2023, 43(7): 2200-2208.
[6]	Fangshu CHEN, Wei ZHANG, Xiaoming HU, Yufei ZHANG, Xiankai MENG, Linxiang SHI. Dynamic aggregate nearest neighbor query algorithm in weighted road network space [J]. Journal of Computer Applications, 2023, 43(7): 2026-2033.
[7]	Jun LIANG, Zehong HONG, Songsen YU. Image segmentation model based on improved particle swarm optimization algorithm and genetic mutation [J]. Journal of Computer Applications, 2023, 43(6): 1743-1749.
[8]	Xiaoyan ZHANG, Jiayi WANG. Comparison of three-way concepts under attribute clustering [J]. Journal of Computer Applications, 2023, 43(5): 1336-1341.
[9]	Chenghao YU, Runhe QIU. Performance analysis of bit error rate on RIS assisted index modulation cooperative system [J]. Journal of Computer Applications, 2023, 43(11): 3559-3567.
[10]	Erchao LI, Shenghui ZHANG. Dynamic multi-objective optimization algorithm based on adaptive prediction of new evaluation index [J]. Journal of Computer Applications, 2023, 43(10): 3178-3187.
[11]	MA Yongqiang, CHEN Xiaomeng, YU Ziqiang. Range query algorithm for large scale moving objects in distributed environment [J]. Journal of Computer Applications, 2023, 43(1): 111-121.
[12]	Xin XIE, Xianyong ZHANG, Xuanye WANG, Pengfei TANG. Neighborhood decision tree construction algorithm based on variable-precision neighborhood equivalent granules [J]. Journal of Computer Applications, 2022, 42(2): 382-388.
[13]	Yazhou HUA, Linlin DING, Ze CHEN, Junlu WANG, Zhu ZHU. Blockchain construction and query method for spatio‑temporal data [J]. Journal of Computer Applications, 2022, 42(11): 3429-3437.
[14]	WU Yue, LUO Jiangtao, LIU Rui, HU Zhongyin. Video similarity detection method based on perceptual hashing and dicing [J]. Journal of Computer Applications, 2021, 41(7): 2070-2075.
[15]	CUI Shuangshuang, WANG Hongzhi. Implementation method of lightweight distributed index based on log structured merge-tree [J]. Journal of Computer Applications, 2021, 41(3): 630-635.

Temporal shortest path counting query algorithm based on tree decomposition

基于树分解的时序最短路径计数查询算法

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 7

References 29

Related Articles 15

Recommended Articles

Metrics