基于路径适配的大规模RDF数据子图匹配算法

胡新苗; 林穗; 姜文超; 熊梦; 贺忠堂

doi:10.12052/gdutxb.210043

欢迎来到能源电力期刊网！

English Version 期刊登录

您当前的位置：

首页 >

文章列表页 >

基于路径适配的大规模RDF数据子图匹配算法

综合研究 | 更新时间：2026-05-27

- 基于路径适配的大规模RDF数据子图匹配算法
- A Path Adaptation-based Subgraph Matching Algorithm for Large-scale RDF Graph Data
- 广东工业大学学报 2022年39卷第1期页码：50-55
- 作者机构：
  
  1. 广东工业大学计算机学院,广东,广州,510006
  2. 中国科学院云计算产业技术创新与育成中心,广东,东莞,523808
- 作者简介：
  
  胡新苗(1991–)，女，硕士研究生，主要研究方向为大数据、复杂网络和推荐系统
  林穗(1972–)，女，副教授，主要研究方向为复杂网络、云计算和推荐系统，E-mail：linsui@gdut.edu.cn
- 基金信息：
  
  国家重点研发计划项目(2018YFB1003603);广东省自然科学基金资助项目(2018A030313061);广东省科技计划项目(2019B010139001);广州市科技计划项目(201902020016)
- DOI：10.12052/gdutxb.210043
  中图分类号： TP391
- 纸质出版：2022
- 稿件说明：
移动端阅览
胡新苗, 林穗, 姜文超, 熊梦, 贺忠堂. 基于路径适配的大规模RDF数据子图匹配算法[J]. 广东工业大学学报, 2022, 39(1): 50-55.

Hu Xin-miao, Lin Sui, Jiang Wen-chao, et al. A Path Adaptation-based Subgraph Matching Algorithm for Large-scale RDF Graph Data[J]. 2022, 39(1): 50-55.
胡新苗, 林穗, 姜文超, 熊梦, 贺忠堂. 基于路径适配的大规模RDF数据子图匹配算法[J]. 广东工业大学学报, 2022, 39(1): 50-55. DOI： 10.12052/gdutxb.210043.

Hu Xin-miao, Lin Sui, Jiang Wen-chao, et al. A Path Adaptation-based Subgraph Matching Algorithm for Large-scale RDF Graph Data[J]. 2022, 39(1): 50-55. DOI： 10.12052/gdutxb.210043.

摘要

子图查询与匹配是社会网络分析和大规模网络图知识发现中的核心技术

也是决定大规模社会网络分析和知识发现准确性的关键。针对当前大规模图数据环境下子图查询算法准确率低、开销大的问题

提出基于路径适配的子图匹配算法。首先基于路径建立图数据的RDF(Resource Description Framework

资源描述框架)索引; 然后将查询子图分解为一组路径

在分解过程中为每条路径获得一组候选匹配路径; 最后通过k-partition交集图将候选路径连接在一起

从而构建出查询图的结果子图。实验测试了在不同数据集上的路径索引构建时间以及F-measure值

与Spath(Shortest Path

最短路径)算法、Sapper算法和SQM(Subgraph Query Matching

子图查询匹配)算法相比

在处理大规模数据时

该算法的查询准确率提高了15%。

Abstract

Subgraph pattern matching is the core technology in social network analysis and knowledge discovery

and also the key to determine the accuracy of social network analysis and knowledge discovery. In view of the low accuracy and high cost of the subgraph query algorithm based on backtracking in large-scale data graph environment

a subgraph matching algorithm based on path adaptation is proposed. First

an index based on the path RDF (Resource Description Framework) graph is built. Then

the query graph is decomposed into a set of paths

for each path in the process of decomposition to obtain a set of candidate paths. Finally

the candidate paths are concatenated together through the k-partition intersection graph to build the result subgraph of the query graph. Compared with Spath (Shortest Path) algorithm

Sapper algorithm and SQM (Subgraph Query Matching) algorithm

this algorithm improves the query accuracy by 15% when dealing with large-scale data.

关键词

Keywords

references

GUAN H Y, ZHU B, LI G Y, et al . Efficient subgraph matching method based on resource description framework graph segmentation and vertex selectivity [J ] . Journal of Computer Applications, 2019, 39(2): 360-369.

YU J, LIU X M, LIU Y B, et al. Multiple pattern graph correlations for efficient graph pattern matching[C]//2017 IEEE/ACS 14th International Conference on Computer Systems and Applications. Hammamet: IEEE, 2017: 469-474.

GUAN H Y, ZHU B, LI G Y, et al . Efficient subgraph matching method based on structure segmentation of RDF graph [J ] . Journal of Computer Applications, 2018, 38(7): 1898-1904.

MA Z M, CAPRETZ M A M, YAN L. Storing massive resource description framework(RDF) data: a survey [J]. Knowledge Engineering Review, 2016, 31(4): 391-413.

LUO G H, LIN S, JIANG W C. A digital order-preserving-matching algorithm based on binary coding processing [J]. Journal of Guangdong University of Technology, 2017, 34(5): 56-59.

YU J, LIU Y B, ZHANG Y, et al . Survey on large-scale graph pattern matching [J ] . Journal of Computer Research and Development, 2015, 52(2): 391-409.

XU W, SONG W A, FU L Z, et al . Distributed subgraph matching algorithm for large scale graph data [J ] . Computer Science, 2019, 46(4): 28-35.

LI L Y, DONG Y H, SHI W J, et al . SQM: subgraph matching algorithm for single large-scale graphs under Spark [J ] . Journal of Computer Applications, 2019, 39(1): 46-50.

ULLMANN J R. An algorithm for subgraph isomorphism [J]. Journal of the ACM, 1976, 23(1): 31-42.

CORDELLA L P, FOGGIA P. A (sub)graph isomorpism algorithm for matching large graphs [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2004, 26(10): 1367-1372.

HE H, SINGH A K. Graphs-at-a-time: query language and access methods for graph data bases[C]//Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data. New York: ACM, 2008: 405-418.

ZHANG S, LI S, YANG J. GADDI: distance index based subgraph matching in biological networks[C]//Proceedings of the 12th International Conference on Extending Database Technology: Advances in Database Technology. New York: ACM, 2009: 192-203.

ZHANG S, LI J Z, GAO H, et al . Approach for efficient subgraph isomorphism testing for multiple graphs [J ] . Journal of Software, 2010, 21(3): 401-414.

HAN W S, LEE J, LEE J H. TurboISO: towards ultrafast and roubst subgraph isomorphism search in large graph databases[C]//Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data. New York: ACM, 2013: 337-348.

SUN Y H, LI F Y, LI G Y, et al . Multi-pattern matching method for RDF graph [J ] . Computer Engineer and Applications, 2020, 56(13): 84-92.

LI G F, YAN L, MA Z M. An approach for approximate subgraph matching in fuzzy RDF graph [J]. Fuzzy Sets and Systems, 2019, 376: 106-126.

浏览量

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

基于PSI技术的福州市地面形变监测与影响因素分析

基于AAGV-YOLOX模型的输电线路异物检测研究

人工噪声辅助无人机太赫兹安全通信的鲁棒设计

SCA-YOLO: 基于可变形卷积与上下文感知注意力的实时目标检测

具守恒量波动方程的循环双子网物理信息神经网络