|
|
|
| Distributed Parallel Reasoning Algorithm with Rete for RDF Data |
| WANG Jingbin, ZHENG Cuichun |
| College of Mathematics and Computer Science, Fuzhou University, Fuzhou 350108 |
|
|
|
|
Abstract Most of the current distributed parallel reasoning algorithms for resource description framework (RDF) data need multiple MapReduce tasks. However, the reasoning of instances of triple antecedents under resource description framework schema (RDFS) /ontology web language (OWL) rules can not be performed expeditiously by some of these algorithms during processing massive RDF data, and the overall efficiency in reasoning process is not satisfactory. To solve this problem, a distributed parallel reasoning algorithm with Rete for RDF data on MapReduce (DRRM) is proposed to perform reasoning on distributed systems. Firstly, lists of schema triples and models for rule markup with the ontology of RDF data are built,and then alpha stage and beta stage of Rete algorithm are implemented with MapReduce at the phase of RDFS/OWL reasoning. Finally, the dereplication of reasoning results is conducted and a whole reasoning procedure of all the RDFS/OWL rules is executed. Experimental results show that the results of parallel reasoning for large-scale data can be achieved efficiently and correctly by the proposed algorithm.
|
|
Received: 27 April 2015
|
About author:: 汪璟玢(通讯作者),女,1973年生,硕士,副教授,主要研究方向为海量数据管理、网络数据库、智能技术.E-mail:wjbcc@263.net.
(WANG Jingbin(Corresponding author), born in 1973, master, associate professor. Her research interests include big data management, network database and intelligence technology.)
郑翠春,女,1989年生,硕士研究生,主要研究方向为海量数据管理、智能技术.E-mail:software_cui@sina.com.
(ZHENG Cuichun, born in 1989, master student. Her research interests include big data management and intelligence technology.) |
|
|
|
[1] 施惠俊.基于云计算的海量语义信息并行推理方法研究.硕士学位论文.上海:上海交通大学, 2012.
(SHI H J. Research of Massive Semantic Information Parallel Inference Method Based on Cloud Computing. Master Dissertation. Shanghai, China: Shanghai Jiao Tong University, 2012.)
[2] 李慧颖,瞿裕忠.基于关键词的语义网数据查询研究综述.计算机科学, 2011, 38(7): 18-23, 50.
(LI H Y, QU Y Z. Keyword-Based Search on Semantic Web Data: The State of the Art. Computer Science, 2011, 38(7): 18-23,50.)
[3] LIU C, QI G L, WANG H F, et al. Large Scale Fuzzy pD* Reasoning Using MapReduce // Proc of the 10th International Semantic Web Conference. Bonn, Germany, 2011, I: 405-420.
[4] 刘 畅.基于大规模模糊RDF数据的推理引擎.硕士学位论文.上海:上海交通大学, 2012.
(LIU C. Large Scale Fuzzy RDF Reasoning Engine. Master Dissertation. Shanghai, China: Shanghai Jiao Tong University, 2012.)
[5] LIU C, QI G L, WANG H F, et al. Reasoning with Large Scale Ontologies in Fuzzy pD* Using MapReduce. IEEE Computational Intelligence Magazine, 2012, 7(2): 54-66.
[6] WU K J. Parallelizing Description Logic Reasoning. Ph.D Dissertation. Quebec, Canada: Concordia University, 2014.
[7] KOTOULAS S, OREN E, VAN HARMELEN F. Mind the Data Skew: Distributed Inferencing by Speeddating in Elastic Regions // Proc of the 19th International Conference on World Wide Web. Raleigh, USA, 2010: 531-540.
[8] OREN E, KOTOULAS S, ANADIOTIS G, et al. MARVIN: Distributed Reasoning over Large-Scale Semantic Web Data. Web Semantics: Science, Services and Agents on the World Wide Web, 2009, 7(4): 305-316.
[9] KOLOVSKI V, WU Z, EADON G. Optimizing Enterprise-Scale OWL 2 RL Reasoning in a Relational Database System // Proc of the 9th International Semantic Web Conference. Shanghai, China, 2010: 436-452.
[10] WU K J, HAARSLEV V. Parallel OWL Reasoning: Merge Classification // Proc of the 3rd Joint International Conference on Semantic Technology. Seoul, Republic of Korea, 2013: 211-227.
[11] LIU C, URBANI J, QI G L. Efficient RDF Stream Reasoning with
Graphics Processing Units (GPUs) // Proc of the 23rd International
World Wide Web Conference. Seoul, Republic of Korea, 2014: 343-344.
[12] URBANI J, PIRO R, VAN HARMELEN F, et al. Hybrid Rea-soning on OWL RL. Semantic Web, 2014, 5(6): 423-447.
[13] AZWARI S A, WILSON J N. The Cost of Reasoning with RDF Updates // Proc of the IEEE International Conference on Semantic Computing. Anaheim, USA, 2015: 328-331.
[14] LIU B, HUANG K M, LI J Q, et al. An Incremental and Distributed Inference Method for Large-Scale Ontologies Based on MapReduce Paradigm. IEEE Trans on Cybernetics, 2014, 45(1): 53-64.
[15] 顾 荣,王芳芳,袁春风,等.YARM:基于MapReduce的高效可扩展的语义推理引擎.计算机学报, 2015, 38(1): 74-85.
(GU R, WANG F F, YUAN C F, et al. YARM: Efficient and Scalable Semantic Reasoning Engine Based on MapReduce. Chinese Journal of Computers, 2015, 38(1): 74-85.)
[16] URBANI J, KOTOULAS S, MAASSEN J, et al. WebPIE: A Web-Scale Parallel Inference Engine Using MapReduce. Web Semantics: Science, Services and Agents on the World Wide Web, 2012, 10: 59-75.
[17] URBANI J, KOTOULAS S, MAASSEN J, et al. OWL Reasoning with WebPIE: Calculating the Closure of 100 Billion Triples // Proc of the 7th Extended Semantic Web Conference. Heraklion, Greece, 2010, I: 213-227.
[18] URBANI J. On Web-Scale Reasoning. Ph.D Dissertation. Amsterdam, Netherlands: Vrije Universiteit, 2013.
[19] WEAVER J, HENDLER J A. Parallel Materialization of the Finite RDFS Closure for Hundreds of Millions of Triples // Proc of the 8th International Semantic Web Conference. Washington, USA, 2009: 682-697.
[20] FORGY C L. Rete: A Fast Algorithm for the Many Pattern/Many Object Pattern Match Problem. Artificial Intelligence, 1982, 19(1): 17-37.
[21] 张 琦.基于MapReduce的分布式规则匹配系统的研究与实现.硕士学位论文.杭州:浙江大学, 2011.
(ZHANG Q. The Research and Implementation of MapReduce-Based Distributed Rule Matching System. Master Dissertation. Hangzhou, China: Zhejiang University, 2011.)
[22] GUO Y B, PAN Z X, HEFLIN J. LUBM: A Benchmark for OWL Knowledge Base Systems. Web Semantics: Science, Services and Agents on the World Wide Web, 2005, 3(2/3): 158-182.
[23] AUER S, BIZER C, KOBILAROV G, et al. DBpedia: A Nucleus for a Web of Open Data // Proc of the 6th International Semantic Web Conference. Busan, Republic of Korea, 2007: 722-735. |
|
|
|
2016, Vol. 29 
