A Path Adaptation-based Subgraph Matching Algorithm for Large-scale RDF Graph Data

Hu Xin-miao; Lin Sui; Jiang Wen-chao; Xiong Meng; He Zhong-tang

doi:10.12052/gdutxb.210043

English Version Journal Login

您当前的位置：

首页 >

文章列表页 >

A Path Adaptation-based Subgraph Matching Algorithm for Large-scale RDF Graph Data

更新时间：2026-05-27

- A Path Adaptation-based Subgraph Matching Algorithm for Large-scale RDF Graph Data
- Vol. 39, Issue 1, Pages: 50-55(2022)
- 作者机构：
  
  1. 广东工业大学计算机学院,广东,广州,510006
  2. 中国科学院云计算产业技术创新与育成中心,广东,东莞,523808
- 作者简介：
- 基金信息：
- DOI：10.12052/gdutxb.210043
  CLC： TP391
- Published：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.

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Energy Management Strategy of Hybrid Locomotive Based on Road Condition Parameters

Ground Deformation Monitoring and Influencing Factors Analysis in Fuzhou City Based on PSI Technology

A Resource Allocation Optimization Method for Multi-UAV Integrated Sensing, Computing, and Communication Towards Disaster Relief

Multi-Scale Contrastive Embedding Enhanced Adaptive Intrusion Detection Model

Modeling of 3D NAND Memory Cells with Taper Angle and Programming Strategy Optimization

Related Author

Yang Chun-yan

Li Zhi-ming

Related Institution

No data

AI问答

⁰