基于资源描述框架图切分与顶点选择性的高效子图匹配方法

doi:10.11772/j.issn.1001-9081.2018061262

计算机应用 ›› 2019, Vol. 39 ›› Issue (2): 360-369.DOI: 10.11772/j.issn.1001-9081.2018061262

基于资源描述框架图切分与顶点选择性的高效子图匹配方法

关皓元, 朱斌, 李冠宇, 蔡永嘉

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

收稿日期:2018-06-19 修回日期:2018-09-11 出版日期:2019-02-10 发布日期:2019-02-15
通讯作者: 朱斌
作者简介:关皓元(1993-),男,辽宁沈阳人,硕士研究生,CCF会员,主要研究方向:智能信息处理;朱斌(1969-),男,辽宁大连人,副教授,硕士,CCF会员,主要研究方向:智能信息处理;李冠宇(1963-),男,辽宁丹东人,教授,博士,CCF会员,主要研究方向:智能信息处理;蔡永嘉(1995-),男,江西乐平人,硕士研究生,CCF会员,主要研究方向:智能信息处理。
基金资助:
国家自然科学基金资助项目（61371090）。

Efficient subgraph matching method based on resource description framework graph segmentation and vertex selectivity

GUAN Haoyuan, ZHU Bin, LI Guanyu, CAI Yongjia

Information Science and Technology College, Dalian Maritime University, Dalian Liaoning 116026, China

Received:2018-06-19 Revised:2018-09-11 Online:2019-02-10 Published:2019-02-15
Supported by:
This work is partially supported by the National Natural Science Foundation of China (61371090).

摘要/Abstract

摘要： 在SPARQL查询过程中，含有复杂结构的资源描述框架（RDF）图的查询效率低下。为此，通过分析几种RDF图的基本结构与RDF顶点的选择性，提出RDF三元组模式选择性（RTPS）——一种基于RDF顶点选择性的图结构切分规则，以提高面向RDF图的子图匹配效率。首先，根据谓词结构在数据图与查询图中的通性建立RDF相邻谓词路径（RAPP）索引，将数据图结构转化为传入-传出双向谓词路径结构以确定查询顶点的搜索空间，并加快顶点的过滤；接着，通过整数线性规划（ILP）问题计算建模将复杂RDF查询图结构分解为若干结构简单的查询子图，通过分析RDF顶点在查询图中的相邻子图结构与特征，确立查询顶点的选择性以确定最优切分方式；然后，通过RDF顶点选择性与相邻子图的结构特征来缩小查询顶点的搜索空间范围，并在数据图中找到符合条件的RDF顶点；最后，遍历数据图以找到与查询子图结构相匹配的子图结构，将得到的子图进行连接并将其作为查询结果输出。实验采用控制变量法，比较了RTPS、RDF子图匹配（RSM）、RDF-3X、GraSS与R3F的查询响应时间。实验结果充分表明，与其他4种方法相比，当查询图复杂度高于9时，RTPS的查询响应时间更短，具有更高的查询效率。

关键词: SPARQL查询处理, 资源描述框架, 子图匹配, 图结构切分, 顶点选择性

Abstract: As the graph-based query in SPARQL query processing becames more and more inefficient due to the increasing structure complexity of Resource Description Framework (RDF) in the graph, by analyzing the basic structure of RDF graphs and the selectivity of the RDF vertices, RDF Triple Patterns Selectivity (RTPS) was proposed to improve the efficienccy of subgraph matching for graph with RDF, which is a graph structure segmentation rule based on selectivity of RDF vertices. Firstly, according the commonality of the predicate structure in the data graph and the query graph, an RDF Adjacent Predicate Path (RAPP) index was built, and the data graph structure was transformed into incoming-outgoing predicate path structure to determine the search space of query vertices and speed up the filtering of RDF vertices. Secondly, the model of Integer Linear Programming (ILP) problem was built to divide a RDF query graph with complicated structure into several query subgraphs with simple structure. By analyzing the structure characteristics of the RDF vertices in the adjacent subgraphs, the selectivity of the query vertices was established and the optimal segmentation method was determined. Thirdly, with the searching space narrowed down by the RDF vertex selectivity and structure characteristics of adjacent subgraphs, the matchable RDF vertices in the data graph were found. Finally, the RDF data graph was traversed to find the subgraphs whose structure matched the structure of query subgraphs. Then, the result graph was output by joining the subgraphs together. The controlling variable method was used in the experiment to compare the query response time of RTPS, RDF Subgraph Matiching (RSM), RDF-3X, GraSS and R3F. The experimental results show that, compared with the other four methods, when the number of triple patterns in a query graph is more than 9, RTPS has shorter query response time and higher query efficiency.

Key words: SPARQL query processing, Resource Description Framework (RDF), subgraph matching, graph structure segmentation, vertex selectivity

中图分类号:

TP181
TP311

关皓元, 朱斌, 李冠宇, 蔡永嘉. 基于资源描述框架图切分与顶点选择性的高效子图匹配方法[J]. 计算机应用, 2019, 39(2): 360-369.

GUAN Haoyuan, ZHU Bin, LI Guanyu, CAI Yongjia. Efficient subgraph matching method based on resource description framework graph segmentation and vertex selectivity[J]. Journal of Computer Applications, 2019, 39(2): 360-369.

参考文献

[1] 黄映辉,李冠宇.语义物联网:物联网内在矛盾之对策[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.)
[2] GROBE M. RDF, Jena, SparQL and the ‘Semantic Web’[C]//Proceedings of the 37th Annual ACM SIGUCCS Fall Conference on User Services. New York:ACM, 2009:131-138.
[3] LIU C, WANG H, YU Y, et al. Towards efficient SPARQL query processing on RDF data[J]. Tsinghua Science and Technology, 2010, 15(6):613-622.
[4] VILLAZON-TERRAZAS B, GARCIA-SANTA N, REN Y, et al. Knowledge graph foundations[M]//Exploiting Linked Data and Knowledge Graphs in Large Organisations. Cham:Springer, 2017:17-55.
[5] 关皓元, 朱斌, 李冠宇, 等. 基于RDF图结构切分的高效子图匹配方法[J].计算机应用,2018,38(7):1898-1904,1909. (GUAN H Y, ZHU B, LI GUAN Y, et al. Eifficient subgraph matching method based on structure segmentation of RDF graph)[J]. Journal of Computer Applications, 2018, 38(7):1898-1904, 1909.)
[6] NEUMANN T, WEIKUM G. RDF-3X:a RISC-style engine for RDF[J]. Proceedings of the VLDB Endowment, 2008, 1(1):647-659.
[7] 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.
[8] LYU X, WANG X, LI Y-F, et al. GraSS:an efficient method for RDF subgraph matching[C]//Proceedings of the 16th International Conference on Web Information Systems Engineering, Part I, LNCS 9418. Berlin:Springer, 2015:108-122.
[9] BUNKE H. Graph matching:theoretical foundations, algorithms, and applications[C]//Proceedings of the 2000 Vision Interface. Montreal:[s.n.], 2000:82-88.
[10] CONTE D, FOGGIA P, SANSONE C, et al. Thirty years of graph matching in pattern recognition[J]. International Journal of Pattern Recognition and Artificial Intelligence, 2008, 18(3):265-298.
[11] KALAYCI E G, KALAYCI T E, BIRANT D. An ant colony optimisation approach for optimising SPARQL queries by reordering triple patterns[J]. Information Systems, 2015, 50:51-68.
[12] 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.
[13] BROEKSTRA J, KAMPMAN A, van HARMELEN F. Sesame:a generic architecture for storing and querying RDF and RDF schema[C]//Proceedings of the 2002 First International Semantic Web Conference, LNCS 2342. Berlin:Springer, 2002:54-68.
[14] 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.
[15] 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.
[16] ZOU L, ÖZSU M T, CHEN L, et al. gStore:a graph-based SPARQL query engine[J]. The VLDB Journal, 2014, 23(4):565-590.
[17] RIVERO C R, JAMIL H M. Efficient and scalable labeled subgraph matching using SGMatch[J]. Knowledge and Information Systems, 2017, 51(1):61-87.
[18] HE H, SINGH A K. Graphs-at-a-time:query language and access methods for graph databases[C]//Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data. New York:ACM, 2008:405-417.
[19] 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.
[20] GUO Y, PAN Z, HEFLIN J. LUBM:A benchmark for OWL knowledge base systems[J]. Journal of Web Semantics:Science, Services and Agents on the World Wide Web, 2005,3(2/3):158-182.

基于资源描述框架图切分与顶点选择性的高效子图匹配方法

Efficient subgraph matching method based on resource description framework graph segmentation and vertex selectivity

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 8

编辑推荐

Metrics

[1]	杨程, 陆佳民, 冯钧. 分布式环境下大规模资源描述框架数据划分方法综述[J]. 计算机应用, 2020, 40(11): 3184-3191.
[2]	李龙洋, 董一鸿, 施炜杰, 潘剑飞. SQM:基于Spark的大规模单图上的子图匹配算法[J]. 计算机应用, 2019, 39(1): 46-50.
[3]	关皓元, 朱斌, 李冠宇, 赵玲. 基于RDF图结构切分的高效子图匹配方法[J]. 计算机应用, 2018, 38(7): 1898-1904.
[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.