Data Science and Engineering (DSE)是由中国计算机学会(CCF)主办，数据库专业委员会承办，施普林格·自然(Springer Nature)集团出版的开放获取(OA)期刊。本篇文章精选自DSE第8卷第1期发文，由中新赛克赞助文章处理费。
文章题目
An Efficient Algorithm of Star Subgraph Queries on Urban Traffic Knowledge Graph
文章介绍
知识图谱在计算机科学领域有着广泛的应用。城市交通知识图谱可以完全记录知识的变化过程，保证知识的即时性和有效性。但是目前关于城市交通知识图谱的构建方案和查询方法的相关工作相对较少。现有的子图查询算法主要集中在图的拓扑结构上，为了构建和查询城市交通知识图谱，不仅要考虑城市交通知识图谱的拓扑结构，还要考虑城市交通知识图谱本身的时间和空间特征。针对此文章提出了一个关于城市交通知识图谱的星形子图查询算法。星形图是一个由星形中心节点和它们的相邻节点组成的图。在星形图中，星形中心节点可以完全描述相邻节点的特征信息。文章收集路网数据和轨迹数据，并从中提取城市交通知识。基于这些知识，构建了一个城市交通的知识图谱。实验结果显示了这种方法的优势。论文的主要贡献如下：
（1） 收集了包含时间和空间特征的数据，如路网数据和轨迹数据。并且从这些包含时间和空间特征的数据中提取城市交通知识图谱中所需要的知识，从而构建城市交通知识图谱。
（2） 探索并研究了城市交通知识图谱上的星形子图的查询模式。在此基础上，提出了一种基于城市交通知识图谱的高效星形子图查询算法TKG_Sub。该算法使用过滤机制来排除时间范围超出数据图谱的查询，提高了在具有时间特征的城市交通知识图谱上的查询效率。
（3） 在构建的城市交通知识图谱上运行TKG_Sub和其他三种子图查询算法，测试和比较TKG_Sub的查询效率。实验结果表明，文章所提的方法比其他算法的查询响应时间要短。
实验效果
论文收集了具有空间和时间特征的数据，如南京路网数据和南京出租车数据集。中心节点是城市交通知识图谱中路网层的交叉口实体，相邻节点是城市交通知识图谱中路网层的路段实体。文章将实验分为两个方面，并且对星形子图查询方法的效率进行了实验。
第一个方面是有一个中心节点的星形查询模式，设置了三组不同的星形查询，中心节点只有一个，相邻节点分别为3、4、5。图1描述了一个有一个中心节点的星形查询的查询响应时间。可以看出，随着查询图中节点和边的数量增加查询所花费的时间以缓慢的速度增加。主要原因是在查询过程中，需要更多的时间来匹配城市交通知识图谱中具有更多节点的查询子图。
图1.有一个中心节点的星形查询的平均查询响应时间
第二个方面是对于具有多个中心节点的星形查询模式，设置了四组不同的星形查询，中心节点分别为2、3、4、5，相邻节点分别为8、11、18、22。由图2可知：随着查询图中节点和边的数量增加，在查询中花费的时间也以适度的速度增加。主要原因是查询图中的中心节点越多，在查询过程中需要比较的顶点和边就越多，查询算法需要更多的时间。
图2.具有多个中心节点的星形查询的平均查询响应时间
将TKG_Sub算法与Ullmann算法、MPMatch算法和FAST算法进行对比，比较不同算法对同一查询图的查询响应时间来测试查询效率。图3、4表明，当查询图是一个有一个中心节点的星形查询图时，随着查询节点数增加时，Ullmann算法的查询响应时间增加得更快，而且增长率超过了其他三种算法。TKG_Sub、MPMatch和Fast的查询时间都以缓慢的速度增加，但TKG_Sub的查询效率较高。
图3.TKG_Sub、MPMatch和Fast在有一个中心节点的星形查询模式下的实验结果
图4.TKG_Sub和Ullmann在有一个中心节点的星形查询模式下的实验结果
但是当查询图是一个具有多个中心节点的星形查询图时，所有算法的查询响应时间都在增加，然而TKG_Sub的查询时间增长速度比其他方法小。如图5，6所示：
图5.TKG_Sub、MPMatch和Fast在有多个中心节点的星形查询模式下的实验结果
图6.TKG_Sub和Ullmann在有多个中心节点的星形查询模式下的实验结果
如图7、8所示，在有288个节点的模拟查询图的条件下，TKG_Sub具有最小的查询响应时间，Ullmann具有最大的查询时间。TKG_Sub的查询效率分别比MPMatch和Fast高21.5%和32.1%，比Ullmann高95%。
图7.TKG_Sub、MPMatch和Fast在模拟查询图方面的实验比较结果
图8.TKG_Sub和Ullmann在有288个节点的星形查询模式下的实验比较结果
结语
论文利用路网数据和轨迹数据提取城市交通知识，构建了一个城市交通知识图谱，并且在城市交通知识图谱上提出了一种星形子图查询算法。用于增强城市交通知识图谱的构建和查询方法的研究，具有提高城市交通知识图谱相关领域的研究意义。文献所提出的基于城市交通知识图谱的高效星形子图查询算法TKG_Sub的查询效率相对于其他三种查询方法要好。
作者简介
孙滔，男，南京航空航天大学硕士。主要研究领域为知识图谱。
许建秋，男，博士，南京航空航天大学计算机科学与技术学院教授、硕士生导师。主持国家自然科学基金青年基金1项，省部级项目3项，以第一作者及通信发表学术论文近30篇（主要为CCF A、B、C类期刊和会议），如IEEE TKDE、Geoinformatica、Information System、PVLDB(demo)、ICDE、IEEE MDM等，出版英文专著1本，软件著作权2项。
胡彩平，男，江苏省南京市金陵工学院计算机工程系讲师。主要承担《数据结构与算法》、《数据库系统原理》等课程的教学任务。参与完成了《机器学习与智能决策支持系统》、《高等数学计算机实验》以及《长江经济带生态环保年鉴》等书的编写工作。在计算机研究与发展、中国图像图形学报以及模式识别与人工智能等国内外权威性刊物以及国际学术会议上已发表学术论文10多篇。作为主要成员参加了多项国家自然科学基金、国家863项目以及省部级科学基金和高科技计划项目。
期刊简介
Data Science and Engineering（DSE）是由中国计算机学会（CCF）主办、数据库专业委员会承办、施普林格 自然（Springer Nature）出版的Open Access期刊。为了迎合相关领域的快速发展需求，DSE致力于出版所有和数据科学与工程领域相关的关键科学问题与前沿研究热点，以大数据作为研究重点，征稿范畴主要包括4方面：（1）数据本身，（2）数据信息提取方法，（3）数据计算理论，和（4）用来分析与管理数据的技术和系统。
目前期刊已被EI、ESCI与SCOPUS收录，CiteScore 2021为6.4，在Computer Science Applications领域排名# 157/747（位列前21%）。稿件处理费由赞助商中新赛克（Sinovatio）承担，欢迎大家免费下载阅读期刊全文，并积极投稿。
原文链接：
https://link.springer.com/article/10.1007/s41019-022-00198-0
