论文研究-基于Hadoop的RDF数据存储及查询优化.pdf

所需积分/C币:10 2019-07-22 22:57:32 1019KB .PDF

随着资源描述框架(resource description framework,RDF)数据量的快速增长,利用分布式的方法来存储和管理大规模RDF数据成为当前的研究热点。为了实现对海量RDF数据的高效存储和查询,研究了RDF三元组在分布式平台Hadoop中的存储和查询方法,提出了一种新的基于Hadoop的RDF数据处理优化方法,通过采用基于HBase混合式数据布局方法以及引入MapReduce 连接查询的I/O代价模型来对海量RDF数据的查询进行优化。在LUBM 标准测试数据集中进行了实验,结果表明该方法能够在保证空间效率的前提下,有效地提高复杂查询的效率。
杀德智,等导:基于且 adop的R薮据存槠及登琦优化 Colu 对于map任务,需要本地读取数据一次,对其进行相应的 操作后,生成ma的结果数据集。图1中结果数据集共经历了 表2描述了 SPARQL子句中不同的三元组模式与 HBase三次读写,而在map阶段中并无网络传输发生,由此可计算出 表之间的查询映射关系。其中,含有“?”的成分代表变量。 该阶段的本地JO量C和网络O量CM,如式(2)所示。 表2 SPARQL三元组模式与 HBase表映射关系 C=lu+30,C=0 三元组模式 HBase表 元组模式 HBase表 若mp任务之后没有 reduce任务,则只需本地读取数据 次,对其进行相应的操作后,将生成的结果数据集写入分布 any (?s,P,o) (s,?p,?o) SP O 式文件系统,因此该阶段的本地LO量C和网络O量CW 如式(3)所示。 P 如表2所示,当三元组模式均为变量或均为已知量时,可 对于 reduce任务, reducer在 shuffle阶段先将 mapper产生 以对任意张表进行检索。当三元组模式中只有个变量且的中间数据集通过网络复制到本地,且经历了一次内存和磁盘 变量不是谓词时,可以直接检索谓词表,当变量是谓词时,则检混合式的排序和合并,最终输人到rdce函效中进行相应的 索OS_P表;当三元组模式中有两个变量时,如(?s,?p,o),利操作,并将生成的输出数据集写入分布式文件系统。显然,此 用 HBase的Scan区域检索机制,根据已知值o在表OS_P的行处的输入数据集应为 mapper输出数据集Ou,山此计算出 键区间内扫描,得到查询结果。 该阶段的本地LO量CR和网络O量C,如式(4)所示。 对数据进行划分后,本文还采用H2RDF系统的方法(数 CR=(1+A)xln+On×CP=l (4) 据编码以及 Snappy压缩算法)来进一步优化存储空间,具 连接查询算法的L0分本地LO和网络0两种,两者代 体过程参考该文献。 价不同。因此,本文为它们分别设置了权重,将两者的加权和作 为算法整体的L0代价(见式(5),并以此作为算法选择的依 4基于 MapReduce的查询策略 据。因此,假设 Mapreduce模型有n的阶段,那么其LO代价为 连接运算是查询中代价最高的部分,因此RDF的查询优 cot=a1×C+o,×CN=S.(a×Cn+2xC 化处理研究也主要集中在连接运算的优化上。连接顺序优化 权重的具体取值由运行环境以及具体需求确定。本地每 是连接运算优化中的一个关键问题,一般通过诜择率的估计来页数据平均访问代价(与ω1有关)与网络单位数据传输代价 进行优化。然而宋杰等人认为分布式环境下的连接查询(与ω,有关)的比值在广域网环境下为1:20,局域网环境下 的性能取决于L0代价(包括本地和网络10),因此,他们提为1:1.6。可见,在广域网环境,以传输代价为主;在局域网环 出了一个 MapReduce连接查询的LO代价模型,并证明了该境,需综合考虑传输代价和本地代价。大部分 Mapreduce集 模型的有效性。本文采用基丁贪心的策略来选择连接变量,然群均采用局域网络环境,因此,ω1:3=1:1.6。 后将具有相同连接变量的三元组模式的相关数据在 Maple- L/O代价确定后,就可以生成查询执行计划。n元连接执 duce中实现多元连接,引入上文提到的JO代价模型米选择行计划选择算法是一种典型的搜索算法,当n较小时,执行计 连接顺序,即最优执行计划 划选择算法是可行的;但当n较大时,搜索空间呈指数级增长。 L/O代价模型是一个计算模型,其中涉及到较多参数。在因此,采用动态规划算法求解是较好的解决方案。动态规划算 RDF数据查询的实际应用中,可将这些参数分为两类:一类可法将待求解的问题分解为若干个子问题(阶段),按顺序求解 以根据数据特征和查询作业特征育接获取,如数据量、记录条子问题,前一子问题的解为后一子问题的求解提供了有用的信 数、投影率等;另类参数的确定则较为复杂,如连接率、选择息。在求解任意子问题时,列出各种可能的局部解,通过决策 率等6。这些参数的具体获得方法木文不螯述,而是侧重保留那些有可能达到最优的局部解,丢弃其他局部解。 介绍连接查询各阶段的基于 Map reduce框架的数据读写情 况的LO计算,如图1所示(设第;个任务的输入以及输出数5实验及结果分析 据量分别为l和O)。 5.1实验环境 sort reduce ph 本文采用 Hadoop2.6.0以及 HBase1.0在五台PC机(In map task partition sort and reduce task el酷睿双核CPU,4GB内存,320GB硬盘空间)上搭建实验环 ill to disk memory 泪 境,其中 Hadoop作为运行平台, HBase用来存储RDF数据。 mp-口 5.2系统结构 y on disk 系统结构如图2所示。具体步骤解释如下: partitions mixture of in-memory and on-disk data a)数据集通过 Mapreduce任务使用 Bulk load方式导入到 other maps HBase中。 Bulkload利用 H Base的数据信息按照特定格式存 图1 Mapreduce过程数据读写 储在HDFS内这一原理,直接在HDFS中生成持久化的HFle 由图1可以看出,对于分发阶段的数据分发任务,需要本数据格式文件,再上传至合适位置,即完成巨量数据快速入库 地读取数据一次,然后经过网络派发(Nm-1)次,所以该阶段的办法。配合 Mapreduce完成,高效便捷,而且不占用 region 的本地LO量C和网络10量CD的计算公式为 资源,增添负载,在人数据量写入时能极人地提高写入效率,并 降低对 HBase节点的写人压力。 b)对索引进行ID编码以及对数据进行压缩。⑩编码是6结束语 指将索引的I前缀长度设为非固定的、类似赫夫曼编码的方 本文研究了基于 Hadoop平台的多种RDF存储方法,提出 式,从而节省了位数,可以表示更多数目的m。数据压缩是指了一种混合式布局存储方案,并首次引入了 MapReduce连接 采用 oogle snappy3(也称py)算法米对 H Base的表进行查询的LO代价模型。本文提出的存储方案在时间效率和空 进一步的压缩。 间效率上达到了一种较好的平衡,但设计实现较为复杂。在查 用户发出查询指令时,根据LO代价模型计算出该查询的询优化方面,本文将 MapReduce连接查询的o代价模型引 LO代价,用动态规划算法选择最优查询计划并在 Map reduce到RDF数据查询中。丙为在分布式环境下,/O代价对查 任务中执行,得到查询结果后返回给用户。 询性能带来的影响已经超过连接运算本身对性能的影响,而很 多研究者并未意识到这一点。但该模型并不是针对RDF数据 的査询提出的,所以还有待进行相应的修正。另外,本文提出 查询结果 的方案对于简单查询的处理上与当前最优的H2RDF系统还存 SPARQL查询 语句 在定的差距。可以看出,基于 Hadoop的海量RDF数据的存 储和查询研究还有许多问题需要进行更加深人的探讨,比如寻 1(①/O代价评估 查询计划 查询执行) 找一种更加简单而高效的数据划分策略以及将分布式计算领域 查洵处理 MapReduce任务执行 的前沿研究引人RDF数据处理领域从而取得更优的查询性能。 MapReduce 参考文献: N)F数据集批量导人HBe编码&压wv [1]杜方,陈跃国,杜小勇.RDF数据查洵处理技术综述[J].坎件学 数据处理 报,2013,24(6):1222-1242. 图2系统结构 [2] RDF concepts and abstract syntax[ EB/OL].[2014-02-25].ht tp://www.w3.org/tr/rdf-coNcePts 5.3实验结果分析 [3] Antoniou g, Van harmelen e.语义网基础教程[M]、陈小平,译 本实验采用LUBM标准测试数据集进行了测试。分别 北京:机械工业出版社,2008 将LUBM1k、 LUBMIOk及LUBM20k数据集通过 Mapreduce[4]BirC, Lehmann, Kobilarov g,cat, DBpedia; a crystallization 务批量导入 HBase,并将处理后的数据集大小与原数据集大小 point for the Web of data[ J]. Web Semantics: Science, Services 以及H2RDF+系统处理后的数据集大小进行了比较,比较结 nd Agents on the World Wide Web, 2009, 7(3): 154-165 果如表3所示。 [5]w3c.spArqLquerylanguageEb/oL.[2013-03-21.https:// www.w3.ory/tr/sparylL 表3薮据集存储容量比较 /GB [6]邹磊,陈跃国.海量RDF教据管理[冂].中囻计算机学会通讯, 数据集原始大小H2RDFH2RDF+ Our sys 2012,8(11):32-43 LUBMIk [71 White T. Hadoop the definitive guide[ M].S1.: O'Reilly Media LUBMIOk Inc.2012 LUBM2Ok 549 529 121 109 [8 Myung J, Yeon J, Lee S. SPARQL basic graph pallern processig 本文采用结合谓词垂直划分以及全索引的混合存储方式。 with iterative MapReduce[ C]//Proc of Workshop on Massive Data 从表3可以看出,与采用仝索引的H2RDF+相比,空间效率有 Analytics on the Cloud. New York ACM Press, 2010:6 了一定的提高。在査询执行效率上,本文选取六条测试语句在 [91 Sun Jianling, Jin Qiang. Scalable RDF store based on HBase and Map reduce[ c] //Proc of the 3rd International Conference on Ad 不同大小的数据集上进行了测试,并与提供查询接口的 vanced Compuler Theory and Engineering. New York: IEEE Press H2RDF系统进行了对比。五次测试的平均时间如表4所示。 2010:633-636 表4查询执行时间比较 [10 Wciss C, Karras P, Bcrnstcin A. Hexastorc: sextuple indexing for sc- UBMIOk LUBM2Ok mantic Web data management J. Proceedings of the VLDB En- 查询 HoRDE Our_Sy comment,2008,1(1):1008-1019 0.6 0.6 1.5 [1l]李国鼎,冯志勇,饶国政,竽.基于BSP的 SPARQL基本图模式 417 709 查询算法[冂.计算机工程,2014,40(9):37-41 0.8 0.9 8 12 Papailiou N, Tsoumakos D, Konstantinou l, et al. H, RDF +: an cf 2.5 ficient data management system for big RDF graphs C]//Proc of 1.9 2.0 ACM SIGMOD International Conference on Management of Data. New 651 596 York: ACM Press, 2014: 909-912 由表4可知,在简单查询下,本系统与H2BDF系统相比并[13: Snappy[ eB/Olj.htps: code. google. com/p/snappy/ 不具有时间性能上的优势,但在复杂查询Q2和Q9下比14王林彬,蔡建样,沈志宏,基于N0L的BDF数据有储与查询 H2RDF快。这是因为H2RDF将简单查询和复杂查询分开处 技术综述[J].计算机应用研究,2015,32(5):1281-1286 理,简单查询采用集中式的查询方法,在一个节点完成,而复卖[15: Papailiou n, Konstantinou, Tsoumakos d,e.H2RDF: adaptive query processing on rdf data in the cloud[ c]//Proc of the 21 st In 查询采用分布式方法。本系统并未对此进行区分,从而导致简 ternational Conference Companion on World wide Web. New York: 单查询效率不尽如人意,但对L/O代价的优化使得本系统在拥 ACM Press,2012:397-400. 有多个连接的复杂查询下具有较好的性能。 (下转第486页) 法将同源的克隆群聚成一簇,再经过同簇克隆群排序得到多版_12」Kuhnλ, Ducasse s,Girb:T. Semantic clustering: identifying topics 本克隆群映射结果。通过人下验证该方法的查全率、查准率及 in source code[ J]. Information Software Technology, 2007 F值均有较高的水平,充分说明了该方法的有效性和可行性。 49(3):230-243 本文的研究工作依然存在一些不足,例如LDA训练时有 [13]Maskeri G, Sarkar S, Heafield K. Mining business topies in source code using latent dirichlet allocation[ C//Proc of the 1st India Soft 些参数值是根据经验设定的,这些设置可能会引起争议,下 warc Enginccring Confcrcncc. New York: ACM Press, 2008: 113-120 阶段将深入研究各参数的影响,最终得到的映射结果更有效地「14]HanⅪiaodωng, Wang xiaolυo, Liu chao. Retrieval method for tracea- 为克隆代码管理、分析提供依据。 bility links between source code and Chinese documentation[ J]. Jour nal of Hefei University of Technology, 2010, 33(2): 188-187 参考文献 15] Thomas S W, Adams B, lassan AE, et al. Studying software evolu 1 Kamiya T, Kusumoto S, Inoue K. CCFinder a multilinguistic token- tion using topic models[ J1. Science of Computer Programming based code clone detection system for large scale source code[J] 2014,80(2):457-479 IEEE Trans on Software Engineering, 2002, 28 (7): 654-670 [16] Asuncion H U, Asuncion A U, Taylor R N. Software traceability with [2]梅宏,王千祥,张路,等.软件分析技术进展[J].计算杌学报, topic modeling[ C]//Proc of IECE Intermational Conference on Soft 2009,32(9):1697-1710 ware engineering. 2010: 95-104 [3] Pate JR, Tairas R, Kraft N A. Clone evolution: a systematic review 17] Nguyen A T, Nguyen TT, Al-Kofahi J, et aL. A topic-based ap [J]. Journal of Software Evolution and Process, 2013, 25 proach for narrowing the scarch spacc of buggy files from a bug report (3):261-283 [C]// Proc of IEEE/ACM International Conference on Automated [4 Kim M, Sazawal V, Notkin D, et aL. An empirical study of code Software Engineering. 2011: 263-272 clone genealogies[C]〃/ Proc of the 1Oth European Software Engi-[18尹丽丽,张丽萍,王春晖,等,基于潜在狄利克雷分配模型预测 neering Conference. New York: ACM Press, 2005: 187-196 克隆代码不-致变化的可能性[J.计算机应用,2014,34(6) [5 Saha R K, Roy C K, Schneider K A. gCad: a near-miss clone gene- 1788-179 alogy extractor to support clone evolution analysisL C∥/ Proc of ieee19钱雨村,彭国军,王滢,等.恶意代码同源性分析及家族聚类 International Confcrencc on Softwarc Maintcnancc.[S.1.]: IEEE [J].计算机工程与应用,2015,51(18):76-81 Press,2013:488-491 [20 Jushi B, Budhathoki P, Woon W L, et aL. Software clone delection [6]Kassas Z M, Bhatti I, Humphreys TE. A graphical approach to GPs using clustering approach C]/ /Proc of Neural Information Proces software-defined receiver implementation[ C]// Proc of Global Confe- sing.[S.1.]: Springer,2015:520-527 rence on Signal and Information Processing. [S.I. 1: IEEE Press, [ 21. Roy C K, Cordy JR. NICAD: accuratc dctection of ncar-misg inten 013:1226-1229 LiOnal clones using flexible prelly-prinLing and code normalization [7] Gode N, Koschke R. Studying clone evolution using incremental clone [Cl//Proc of the 16th IEEE International Conference on Program detection[J]. Journal of Software: Evolution and Process Comprehension. [S 1.]: IEEE Press, 2008: 172-181 13,25(2):165-192 [22 Mimno D, Wallach H M, McCallum A. Gibbs sampling for logistic [8 Ci Meng, Su Xiaohong, Wang Tiantian, et al. A new clone group normal topic models with graph-based priors[ EB/OL].(2008).ht mapping algorithm for extracting clone genealogy on multi-version soft tps: //works. bepress. com/hanna_wallach/7/ warc[C]//Proc of thc 3rd International Confcrencc on Instrumcnta- [23. Zavitsanos E, Petridis S, Paliouras C, ct al. Determining automati tion, Measurement, Computer, Communication and Control. vally the size of learned ontologies[C]//Proe of the 18 th European 1.]: IEEE Press,2013:848-853. Conference on Artificial Intelligence. 2008: 775-776 [9]涂颖,张丽萍,王春晖,等.基于软件多版本演化提取克隆谱系24」 Griffiths t i, Steyvers M. Finding scientific topics冂」·Poce [J].计算机应用,2015,35(4):1169-1173 dings of the National Academy of Sciences, 2004, 101( Suppl 「10]张瑞霞,张丽萍,王春晖,等.基于主题建模技术的克隆群映射 1):5228-5235 方法[冂.计算机工程与设计,2015,36(6):1524-1529 [25 Polzehl J, Spokoiny V. Propagation-separation approach for local like [11 Blei D M, Ng A Y, Jordan M I. Latent dirichlet allocation[ J. Jour- lihood estimation[ J_. Probability Theory and Related Fields nal of Machine Learning Research, 2003, 3(1): 993-1022 2006,135(3):335-362 (上接第480页) [21 Husain M F, McGlothlin J, Masud MM, et aL. Heuristics-based [16]宋杰,李甜甜,朱志良,等. Map reduce连接查询的Ⅳ代价研究 query processing for large RDF graphs using cloud computing [J].软件学报,2015,26(6):1438-1456 IEEE Trans on Knowledge and Data Engineering, 2011, 23 [17] Deal J, Ghemldwal S. MapReduce: simplified dala processing Onl 9):1312-1327 large clusters[J. Communications of the ACM, 2008, 51(1): [22 Um J H, Lee S, Kim TH, et al. Distributed RDF store for efficient 107-113 searching billions of triples based on Hadoop[ J]. The Journal of 18] Guo Yuanbo, Pan Zhengxiang, lleflin J. LUBM: a benchmark for Supercomputing,2016,72(5):1825-1840 OWL knowledge base systems[J]. Web semantics: Science,[23]李韧.基于 Hadoop的大规模语义Wcb本体教括查询与推理关健 Services and Agents on the World Wide Web, 2005, 3(2-3) 技术研究[D].重庆:重庆大学,2013 [24杨健,罗军.基于 Hadoop的RDF数据存储策略综述[J].信息 191 Rohloff K, Schantz R E. High-performance, massively scalable dis- 安全与技术,2015,6(5):46-48 tributed systems using the Mapreduce software framework: the [25. Goasdoue F, Kaoudi 7, Manolescu I, et al. Clique Square flat plans SHARD triplc-storc[ C]//Proc of Workshop on Programming Support for massively parallcl RDF qucrics[ C]//Proc of thc 31 st IEEE Innovations for Emerging Distributed Applications. New York: ACM national Conference on Data Engineering. New York IEee Press.2010:4. 2015:771-78 [20]Li Li, Song Yaqi. Distributed storage of massive RDF data using [26. Abadi D J, Marcus A, Madden S R, et al. Scalable semantic Web HBase[ J]. Journal of Communication and Computer, 2011, 8 data management using vertical partitioning[ C]//Proc of the 33 rd In- (5):325-328 ternational Conference on Very Large Data Bases. 2007: 411-422

...展开详情
img

关注 私信 TA的资源

上传资源赚积分,得勋章
最新资源