分布式RDF关键词近似搜索方法

doi:10.3969/j.issn.0253-2778.2017.10.004

中国科学技术大学学报 ›› 2017, Vol. 47 ›› Issue (10): 823-836.DOI: 10.3969/j.issn.0253-2778.2017.10.004

分布式RDF关键词近似搜索方法

陈远，汪璟玢

福州大学数学与计算机科学学院，福建福州 350108

收稿日期:2016-08-28 修回日期:2016-12-08 出版日期:2017-10-31 发布日期:2017-10-31
通讯作者: 汪景玢
作者简介:陈远，男，1991年生，硕士生.研究方向：数据挖掘.E-mail: 727947930@qq.com
基金资助:
国家自然科学基金（61300104）,福建省科技拥军基金（JG2014001）,福建省自然科学基金（2012J01168）,福州大学科技发展基金(2013-XQ-32)资助.

Distributed keyword approximate search method for RDF

CHEN Yuan, WANG Jingbin

College of Mathematics and Computer Science, Fuzhou University, Fuzhou 350108, China）

Received:2016-08-28 Revised:2016-12-08 Online:2017-10-31 Published:2017-10-31

摘要/Abstract

摘要： 现有的RDF关键词搜索方法主要是在大规模的RDF数据图上直接进行搜索，未能充分利用RDF本体中的语义信息，迭代次数过多造成搜索效率和效果不理想.针对这些问题，借助Redis内存数据库集群，提出分布式RDF关键词近似搜索算法(DKASR)，即在分布式平台上实现大规模数据的并行搜索.算法结合RDF本体的语义信息构建本体子图，利用语义评分函数对本体子图进行排序，借助MapReduce计算模型实现并行搜索并返回Top-k结果；如果返回的结果没有达到Top-k，则对本体子图进行扩展生成近似本体子图，使用语义相似度函数对近似本体子图进行排序，再利用MapReduce计算模型实现并行搜索，直到返回Top-k结果.实验结果表明，DKASR算法能够高效正确地实现RDF关键词近似搜索并有效返回Top-k结果.

关键词: RDF, 关键词, 近似搜索, Redis, MapReduce

Abstract: Existing RDF keyword search methods mainly search on the large-scale RDF data graph directly and do not make full use of the semantic information in the RDF ontology. Too many iterations lead to unfavorable search efficiency and unsatisfactory results. To solve these problems, a distributed keyword approximate search algorithm (DKASR) for RDF based on Redis memory database cluster was proposed and the parallel search of large-scale data on the distributed platform was realized. The algorithm constructs ontology sub-graphs by using the semantic information of RDF ontology, uses the semantic scoring function to sort ontology sub-graphs, and searches and returns the Top-k results concurrently with the aid of MapReduce computation model. If the results do not meet Top-k, ontology sub-graphs are extended to generate approximate ontology sub-graphs and the semantic similarity function is used to sort approximate ontology sub-graphs. Then, MapReduce computation model was used to realize the parallel search until the results meet Top-k. Finally, the results of experiments show that the DKASR algorithm can realize the RDF keyword approximate search and return the Top-k results efficiently and accurately.

Key words: RDF, keyword, approximate search, Redis, MapReduce

中图分类号:

TP391

陈远，汪璟玢. 分布式RDF关键词近似搜索方法[J]. 中国科学技术大学学报, 2017, 47(10): 823-836.

CHEN Yuan, WANG Jingbin. Distributed keyword approximate search method for RDF[J]. Journal of University of Science and Technology of China, 2017, 47(10): 823-836.

参考文献

［1］
刘博. 基于关键词的RDF数据图查询模型研究[D]. 郑州：郑州大学, 2015.
[2] 姜旭,张波.采用RDF的查询扩展研究[J]. 计算机应用与软件, 2011, 28(12):210-212.
JIANG Xu, ZHANG Bo. On query extension using RDF[J]. Computer Applications and Software, 2011, 28(12):210-212.
[3] 董书暕,汪璟玢. HMSST:一种高效的SPARQL查询优化算法[J]. 计算机科学, 2014, S2: 323-326, 336.
DONG Shujian, WANG Jingbin. HMSST: An efficient algorithm for SPARQL query[J]. Computer Science, 2014, S2: 323-326, 336.
[4] 杜方,陈跃国,杜小勇. RDF数据查询处理技术综述[J]. 软件学报, 2013, 24(6): 1222-1242.
DU Fang, CHEN Yueguo, DU Xiaoyong. Survey of RDF query processing techniques[J]. Journal of Software, 2013, 24(6): 1222-1242.
[5] TRAN T, WANG H, RUDOLPH S, et al. Top-k exploration of query candidates for efficient keyword search on graph-shaped (RDF) data[C]// Proceedings of the 25th International Conference on Data Engineering. Shanghai, China: IEEE, 2009: 405-416.
[6] ZENZ G, ZHOU X, MINACK E, et al. From keywords to semantic queries-Incremental query construction on the semantic Web[J]. Journal of Web Semantics, 2009, 7(3): 166-176.
[7] GKIRTZOU K, PAPASTEFANATOS G, DALAMAGAS T. RDF keyword search based on keywords-to-sparql translation[C]// Proceedings of the First International Workshop on Novel Web Search Interfaces and Systems. Melbourne, Australia: ACM, 2015: 3-5.
[8] LE W C, LI F F, KEMENTSIETSIDIS A, et al. Scalable keyword search on large RDF data[J]. IEEE Transactions on Knowledge and Data Engineering, 2014, 26(11): 2774-2788.
[9] 李慧颖,瞿裕忠. KREAG:基于实体三元组关联图的RDF数据关键词查询方法[J]. 计算机学报, 2011, 34(5): 825-835.
LI Huiying, QU Yuzhong. KREAG：Keyword query approach over RDF data based on entity-triple association graph[J]. Chinese Journal of Computers, 2011, 34(5): 825-835.
[10] ELBASSUONI S. Effective searching of RDF knowledge bases[D]. Munchen: Max-Planck-Institut Für Informatik, 2011.
[11] KAOUDI Z, MANOLESCU I. RDF in the clouds: A survey[J]. VLDB Journal, 2015, 24(1): 67-91.
[12] DE VIRGILIO R, MACCIONI A. Distributed Keyword Search Over RDF Via Mapreduce[M]// The Semantic Web: Trends and Challenges. Springer, 2014: 208-223.
[13] 周文健. 基于语义距离的RDF本体查询方法研究[D].沈阳: 东北大学, 2011.
[14] 章登义,吴文李,欧阳黜霏. 基于语义度量的RDF图近似查询[J].电子学报, 2015, 43(7): 1320-1328.
ZHANG Dengyi, WU Wenli, OUYANG Chufei. Approximating query with semantic-based measure on RDF graphs[J]. Acta Electronica Sinica, 2015, 43(7): 1320-1328.

()
(

[1]	苏浩，刘其成，牟春晓. 基于MapReduce的商品评论热点发现算法研究[J]. 中国科学技术大学学报, 2019, 49(2): 112-118.
[2]	蔡勇，陈红梅，. MapReduce环境下基于概念分层的概念格并行构造算法[J]. 中国科学技术大学学报, 2018, 48(4): 275-283.
[3]	王进，王鸿，夏翠萍，欧阳卫华，陈乔松，邓欣. 基于Spark的组合分类器链多标签分类方法[J]. 中国科学技术大学学报, 2017, 47(4): 350-357.

分布式RDF关键词近似搜索方法

Distributed keyword approximate search method for RDF

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 3

编辑推荐

Metrics

本文评价