基于RDF图结构切分的高效子图匹配方法

doi:10.11772/j.issn.1001-9081.2017122950

计算机应用 ›› 2018, Vol. 38 ›› Issue (7): 1898-1904.DOI: 10.11772/j.issn.1001-9081.2017122950

基于RDF图结构切分的高效子图匹配方法

关皓元, 朱斌, 李冠宇, 赵玲

大连海事大学信息科学技术学院, 辽宁大连 116026

收稿日期:2017-12-18 修回日期:2018-01-30 出版日期:2018-07-10 发布日期:2018-07-12
通讯作者: 李冠宇
作者简介:关皓元(1993-),男,辽宁沈阳人,硕士研究生,CCF会员,主要研究方向:智能信息处理;朱斌(1969-),男,辽宁大连人,副教授,硕士,CCF会员,主要研究方向:智能信息处理;李冠宇(1963-),男,辽宁丹东人,教授,博士,CCF会员,主要研究方向:智能信息处理;赵玲(1993-),女,黑龙江佳木斯人,硕士研究生,CCF会员,主要研究方向:智能信息处理。
基金资助:
国家自然科学基金资助项目（61371090）。

Efficient subgraph matching method based on structure segmentation of RDF graph

GUAN Haoyuan, ZHU Bin, LI Guanyu, ZHAO Ling

Faculty of Information Science & Technology, Dalian Maritime University, Dalian Liaoning 116026, China

Received:2017-12-18 Revised:2018-01-30 Online:2018-07-10 Published:2018-07-12
Supported by:
This work is partially supported by the National Natural Science Foundation of China (61371090).

摘要/Abstract

摘要： 针对在SPARQL查询处理中，随着查询图结构逐渐复杂而导致基于图的查询效率愈发低下的问题，通过分析几种资源描述框架（RDF）图的基本结构，提出了一种基于查询图结构切分的子图匹配方法——RSM。首先，将查询图切分为若干结构简单的查询子图，并通过相邻谓词结构索引来定义查询图节点的搜索空间；然后，通过相邻子图结构来缩小搜索空间范围，在数据图中根据搜索空间中的搜索范围找到符合的子图结构；最后，将得到的子图进行连接并作为查询结果输出。将RSM与RDF-3X、R3F、GraSS等主流查询方法作比较，对比了各方法在不同数据集上对于复杂程度不同的查询图的查询响应时间。实验结果充分表明，与其他3种方法相比，在处理结构复杂的查询图时，RSM的查询响应时间更短，具有更高的查询效率。

关键词: SPARQL查询处理, 资源描述框架, 子图匹配, 结构切分, 搜索空间

Abstract: With the complexity increasing of query graph structure, the efficiency of graph-based query in SPARQL query processing becomes lower and lower. By analyzing the basic structure of Resource Description Framework (RDF) graph, a subgraph matching method based on structure segmentation of query graph, called RSM (RDF Subgraph Matching), was proposed. Firstly, a query graph was divided into several simple query subgraphs, and query graph node searching space was defined through structure index of adjacent predicate. Secondly, the searching space was narrowed down by the adjacent subgraph structure, and a matchable subgraph could be found in data graph according to the searching area in the searching space. Finally, the result graph was output by joining related subgraphs. The query response times of RSM, RDF-3X, R3F and GraSS on query graphs with different structural complexity in different data sets were compared. The experimental results show that, compared with the other three methods, RSM has a shorter query response time and higher query efficiency in processing complex query graphs.

Key words: SPARQL query processing, Resource Description Framework (RDF), subgraph matching, structure segmentation, searching space

中图分类号:

TP181
TP311

关皓元, 朱斌, 李冠宇, 赵玲. 基于RDF图结构切分的高效子图匹配方法[J]. 计算机应用, 2018, 38(7): 1898-1904.

GUAN Haoyuan, ZHU Bin, LI Guanyu, ZHAO Ling. Efficient subgraph matching method based on structure segmentation of RDF graph[J]. Journal of Computer Applications, 2018, 38(7): 1898-1904.

参考文献

[1] GROBE M. RDF, Jena, SparQL and the ‘Semantic Web’[C]//Proceedings of the 2009 ACM SIGUCCS Fall Conference on User Services. New York:ACM, 2009:131-138.
[2] 黄映辉,李冠宇.语义物联网:物联网内在矛盾之对策[J].计算机应用研究,2010,27(11):4087-4090.(HUANG Y H, LI G Y. Semantic Web of things:strategy for Internet of things' intrinsic contradiction[J]. Application Research of Computers, 2010, 27(11):4087-4090.)
[3] LYU X D, WANG X, LI Y F, et al. GraSS:an efficient method for RDF subgraph matching[C]//WISE 2015:Proceedings of the 16th International Conference on Web Information Systems Engineering. Berlin:Springer, 2015:108-122.
[4] VILLAZON-TERRAZAS B, GARCIA-SANTA N, REN Y, et al. Knowledge graph foundations[M]//Exploiting Linked Data and Knowledge Graphs in Large Organisations. Berlin:Springer, 2017:17-55.
[5] NEUMANN T, WEIKUM G. RDF-3X:a RISC-style engine for RDF[J]. Proceedings of the VLDB Endowment, 2008, 1(1):647-659.
[6] KIM K, MOON B, KIM H J. R3F:RDF triple filtering method for efficient SPARQL query processing[J]. World Wide Web-Internet & Web Information Systems, 2015, 18(2):317-357.
[7] BUNKE H. Graph matching:theoretical foundations, algorithms, and applications[C]//Proceedings of the 2000 International Conference on Vision Interface. Montreal:[s.n.], 2000:82-88.
[8] CONTE D, FOGGIA P, SANSONE C, et al. Thirty years of graph matching in pattern recognition[J]. International Journal of Pattern Recognition & Artificial Intelligence, 2004, 18(3):265-298.
[9] CORDELLA L P, FOGGIA P, SANSONE C, et al. A (sub)graph isomorphism algorithm for matching large graphs[J]. IEEE Transactions on Pattern Analysis & Machine Intelligence, 2004, 26(10):1367-1372.
[10] ULLMANN J R. An algorithm for subgraph isomorphism[J]. Journal of the ACM, 1976, 23(1):31-42.
[11] HE H, WANG H, YANG J, et al. BLINKS:ranked keyword searches on graphs[C]//Proceedings of the 2007 ACM SIGMOD International Conference on Management of Data. New York:ACM, 2007:305-316.
[12] BROEKSTRA J, KAMPMAN A, HARMELEN F V. Sesame:a generic architecture for storing and querying RDF and RDF schema[C]//ISWC 2002:Proceedings of the First International Semantic Web Conference, LNCS 2342. Berlin:Springer, 2002:54-68.
[13] UDREA O, PUGLIESE A, SUBRAHMANIAN V S. GRIN:a graph based RDF index[C]//Proceedings of the 2007 National Conference on Artificial Intelligence. Menlo Park, CA:AAAI Press, 2007:1465-1470.
[14] YAN X, YU P S, HAN J. Graph indexing:a frequent structure-based approach[C]//Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data. New York:ACM, 2004:335-346.
[15] KIM K, MOON B, KIM H J. RP-filter:a path-based triple filtering method for efficient SPARQL query processing[C]//JIST 2011:Proceedings of the 2011 Joint International Semantic Technology Conference. Berlin:Springer, 2012:33-47.
[16] RIVERO C R, JAMIL H M. Efficient and scalable labeled subgraph matching using SGMatch[J]. Knowledge and Information Systems, 2017, 51(1):61-87.
[17] HE H, SINGH A K. Graphs-at-a-time:query language and access methods for graph databases[C]//SIGMOD 2008:Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data. New York:ACM, 2008:405-418.
[18] HOFFART J, SUCHANEK F M, BERBERICH K, et al. YAGO2:a spatially and temporally enhanced knowledge base from Wikipedia[J]. Artificial Intelligence, 2013, 194:28-61.
[19] FELLBAUM C, MILLER G. WordNet:an electronic lexical database[J]. Library Quarterly Information Community Policy, 1998, 25(2):292-296.

基于RDF图结构切分的高效子图匹配方法

Efficient subgraph matching method based on structure segmentation of RDF graph

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 8

编辑推荐

Metrics

[1]	杨程, 陆佳民, 冯钧. 分布式环境下大规模资源描述框架数据划分方法综述[J]. 计算机应用, 2020, 40(11): 3184-3191.
[2]	关皓元, 朱斌, 李冠宇, 蔡永嘉. 基于资源描述框架图切分与顶点选择性的高效子图匹配方法[J]. 计算机应用, 2019, 39(2): 360-369.
[3]	李龙洋, 董一鸿, 施炜杰, 潘剑飞. SQM:基于Spark的大规模单图上的子图匹配算法[J]. 计算机应用, 2019, 39(1): 46-50.
[4]	黄峻福, 李天瑞, 贾真, 景运革, 张涛. 中文异构百科知识库实体对齐[J]. 计算机应用, 2016, 36(7): 1881-1886.
[5]	爨林娜, 史一民, 李冠宇, 吴学华. 语义物联网中链接传感器数据发布系统[J]. 计算机应用, 2015, 35(9): 2440-2446.
[6]	韩彩丽, 李嘉骏, 张晓培, 肖敏. 基于语义属性特征图的查询扩展方法[J]. 计算机应用, 2015, 35(2): 440-443.
[7]	师雪霖赵英. 基于RDF的语义网格数据建模与检索[J]. 计算机应用, 2008, 28(9): 2324-2327.
[8]	陈家琪陶媛 . 对语义网查询语言的逻辑推理优化[J]. 计算机应用, 2006, 26(12): 2800-2802.