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.
[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.
2018, Vol. 38 
