《基于分级树形索引的关联数据压缩研究-王凯东.pdf》由会员分享，可在线阅读，更多相关《基于分级树形索引的关联数据压缩研究-王凯东.pdf（51页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、rllllll Jlllllll Jlf rl rlll Jlllfllll Jl JI Jlll rflY321 9650分类号!13Q!：学校代码1 0 4i 8学号羔盟垒鳢王f10蛐鬻级武易薹舞净锉夫晕硕士学位论文燕子分级树形索引的关联数据压缩研究学位审请人：学年4专业：指导教师：答辩日期：王凯东计算机科学与技术顾进广万方数据A Dissertation Submitted in Partial Fulfillment of the Requirementsfor the Degree of Master in EngineeringResearch on Hierarchical Tr
2、eeIndex basedLinked Data CompressionMaster Candidate：Major：一 Supervisor：Kaidong WangComputer Science and TechnologyProfJinguang GuWuhan University of Science and TechnologyWuhan，Hubei 430081，PRChinaMay,2017万方数据武汉科技大学研究生学位论文创新性声明IIII I II l U II I II I I II IIIY321 9650本人郑重声明：所呈交的学位论文是本人在导师指导下，独立进行研究
3、所取得的成果。除了文中己经注明引用的内容或属合作研究共同完成的工作外，本论文不包含任何其他个人或集体已经发表或撰写过的作品成果。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。申请学位论文与资料若有不实之处，本人承担一切相关责任。论文作者签名： z钡b寿、 日期：研究生学位论文版权使用授权声明本论文的研究成果归武汉科技大学所有，其研究内容不得以其它单位的名义发表。本人完全了解武汉科技大学有关保留、使用学位论文的规定，同意学校保留并向有关部门(按照武汉科技大学关于研究生学位论文收录工作的规定执行)送交论文的复印件和电子版本，允许论文被查阅和借阅，同意学校将本论文的全部或部分内容编
4、入学校认可的国家相关数据库进行检索和对外服务。论文作者签名： 衫饥糸万方数据摘要随着语义网技术的不断发展和应用，大规模RDF数据集的使用也越来越频繁，在管理这些大规模数据集时，由于RDF数据集的体积问题，查询和管理的性能会受到很大影响。因此，对于大规模RDF数据而言，高效率的存储方法显然是很重要的。对于数据的压缩存储而言，本质上是去除数据里包含的冗余信息内容。目前，对于大规模RDF数据的压缩存储，其处理思路可以分为以下两种：基于数据模型层次的压缩处理和基于序列化层次的压缩处理，其中，基于序列化层次的压缩处理思路又可以细分为语法结构压缩和字符压缩。本文从RDF数据的序列化层次出发，通过对当前RD
5、F压缩存储技术进行分析总结，提出了一种基于关系三维矩阵的分级树形索引压缩模型。该模型利用分析和提取RDF标识间的关系来构建字典，将三元组映射为ID三元组。通过分析关联数据集自身的关系三维矩阵分布结构，结合分级树形索引的存储思路，解决矩阵存储的结构冗余问题，实现对数据集的序列化压缩。此外，本文还分析总结了该压缩模型查询对关联数据基本查询模式的匹配。通过实验验证与结果分析表明，本文提出的压缩存储模型能够有效提高RDF数据的压缩效率，同时也实现了很好的查询效率。关键词：资源描述框架；冗余；三维矩阵；分级树形索引；压缩万方数据AbstractWith the development and appli
6、cation of semantic web，RDF dataset with largescale was using more and more frequentlyWhile manage these large scale datasets，dueto the size problem of these files，the performance of the query operation will be greatlyaffectedTherefore，for large scale RDF data，efficient storage method is clearly very
7、importantFor data compression storage，it is essentially the removal of redundant informationcontained in the datasetAt present，the compression methods of large scale RDF dataCan be divided into the following two types：compression processing based on datamodel level and compression processing based o
8、n serialization level，and compressionprocessing based on serialization level carl be subdivided into syntactic compression andsymbolic compressionIn this thesis，we based on the serialization level of RDF data，by analyzing thecurrent technology of RDF data compression，a compression model based on hie
9、rarchicaltree-index idea and the threedimensional matrice structure has been proposedByanalyzing and extracting the relationship between the URI of RDF to build the dictionaryto map triples into ID triplesBy analyzing the three-dimensional matrice structure oflinked data，combine the idea也at makes hi
10、erarchical treeindex to solve the redundantproblem of matrice structureIn addition，this thesis also analyzes and summarizes therules and performance of query on this modelWith the experimental confmnation andresult analysis，the compression model proposed Can effectively improve thecompression ratio
11、of RDF data,and it also improves the speed of node searchingKeywords：RDF；Redundant；Compression；Threedimensional Matrice；HierarchicalTreeIndexII万方数据目 录摘要。IABSTRACT第1章绪论111研究的背景意义112研究现状213本文的主要工作414本文的结构安排4第2章基本理论与相关知识621 RDF数据模型622关联数据压缩6221数据模型层次压缩7222序列化层次压缩723图模型表示方法824关系三维矩阵表示方法1025本章小结。11第3章 基于
12、分级树形索引的数据压缩1231问题的提出与分析1232模型总体架构1333关联数据字典构建。1434分块数据索引构建。1635分块数据压缩一19351分块数据冗余分析19332分块数据压缩2136压缩数据结构及算法24361基于树形索引的分层结构24362子结点匹配检索25IlI万方数据363关联数据查询模式分析2737本章小结28第4章实验设计与结果分析2941实验数据集。2942理论压缩结果分析。2943实验结果与分析。3 1431压缩率31432查询效率3444本章小结36第5章结论与展望一3751结论3752展望。38致射。39参考文献40附录1攻读硕士学位期间发表的论文44附录2攻读
13、硕士学位期间参加的科研项目45IV万方数据武汉科技大学硕士学位论文11研究的背景意义第1章绪论从互联网诞生到今天，资讯在社会上的构建、组织以及传播的方式相较于以前发生了巨大的变化，而计算机的普及和网络传输速度的大幅度提升也使得当今时代信息的分享和利用获得了巨大的便利。在Webl0时代，信息构建分享的思路是以内容为核心，由网站提供各种内容，而用户根据自己的兴趣对内容检索浏览。而Web20则是在Webl0的基础上改进，以用户为核心，提供各种服务来承载用户创造的内容，并组织用户之间的各种交互，让用户自己共享内容，这也使网络上信息的创造者获得了数量上的飞跃，使网络上数据和信息的规模以极快的速度持续增长
14、。在目前这些传统的信息构建思路里，网络是以文档为中心组织以及分享数据，Web内容的组织方式是将数据渲染为便于人类阅读的信息，而这些信息绝大多数都是半结构化的HTML内容，因为数据量的规模十分巨大，因此如果要对这些信息进行整合利用必须要用到自动化的手段，但是受限于这些内容本身的编码结构，机器很难准确地识别原本实际提供给人类阅读的内容，无法很好地还原和利用数据之间的关系，因此并不能对传统互联网上的信息进行很好的理解处理。而随着Web3Oil】时代的到来，作为其核心内容的语义网【2】对当前的Web内容组织方式提出了颠覆式的革新，也为海量的数据处理提供了新的思路方向。语义网的核心思路是以数据为中心构建
15、网络【3】，即在最初构建数据内容的时候，就使用规范化、语义化且机器可以理解处理的结构来对所需要提供的资源进行语义化描述，通过这些有标准可依的描述，可以建立推理的机制，从而使机器可以对网络上的数据理解并自动化处理，通过对数据间的逻辑关系进行分析和推理，将整个互联网的资源进行整合利用，为知识的管理以及自动化处理提供了巨大的便利。目前，语义网推行资源描述框架(ResourceDescriptionFramework，RDF)【4】作为数据发布和使用的推荐技术标准，它在语义网的语义化查询，信息自动化处理以及关联数据中都有十分重要的作用。RDF是由W3C技术联盟制定的用于描述网络上的资源的技术标准，其目
16、的在于构建一个通用的框架，用于整合不同领域的元数据，从而保证其描述的统一性，这种结构使来自不同领域的资源在互联网上实现链接和处理，因此，近些年来，在很多不同的领域RDF都被广泛应用，网络上发布的RDF数据的数量也越来越多，这些数据模型被用于对资源进行描述处理，同时提供给用户进行下载使用【5】，利用RDF本身的语义结构，资源与资源之间也建立了逻辑联系，万方数据武汉科技大学硕士学位论文在上述基础上形成了基于语义的关联数据，通过对近年来发布的关联数据云图的分析【6】可以发现，在不同领域中的数据集中，现在RDF三元组的数目已经达到了百亿数量级。而其中有些内容比较庞大的数据集，如DBpedia7】，自身
17、就已经包含了超过10亿个RDF三元组。与其他数据类型一样，关联数据也有冗余存在，文献【89】指出这是导致关联数据集体积臃肿的重要因素。关联数据集越来越大的体积意味着需要占用更多的存储空间，数据集的传输和共享也会耗费大量的时间。RDF三元组原本冗长的文本格式对存储空间和传输带宽造成很多浪费，因此，为了减小数据集的体积，提升传输效率，对关联数据进行压缩是很有必要的。12研究现状数据压缩的目的是降低数据文件里的冗余信息，从而缩减数据文件的体积。根据对关联数据集表达的层次划分，RDF数据模型可以分为数据模型层次和序列化层次模型，而对RDF数据集的压缩也是在这两个层次上进行的，由于两个层次上的表示结构不
18、同，因此在这两个层次上对于冗余信息的处理思路也各不相同。而基于对不同层次上的冗余进行分类，文献101将现有的冗余类型分为语法冗余、语义冗余以及字符冗余，而基于不同层次上的冗余信息的处理，又可以将压缩分为数据模型层次压缩以及序列化层次压缩。数据模型层次是数据描述在现实世界的抽象表示。对于RDF数据集而言，数据模型层次上的数据表示本质上是由三元组组成的RDF图的集合。在这个层次上，数据的大小可以通过三元组的数目来计算，因此减少三元组的数目可以达到在这个层次上对数据集进行压缩的目的。而这种可以通过规则推理减少的三元组内容即是前面分类中的语义冗余。对于语义冗余的处理，文献【1l一12根据W3C所提出的
19、关联数据简图【13】的概念，提出了通过推理对关联数据集中的空白结点三元组进行检测，并且去除其中的冗余三元组的算法。MichaelMeier提出了一种基于规则的压缩方法141，通过用户为数据集定义的特定规则进行处理，从而去除与用户需求无关的三元组内容。同样，Pichler也针对该问题提出了压缩方法【15】，通过结合规则、限制条件以及用户查询需求这三个方面的条件对关联数据集中的冗余三元组进行处理。但是，这两种压缩方法是依赖于具体的应用，而且在使用时必须由用户定制规则内容，这使这两种方法局限于特定的适用范围，而不能对其他的大规模数据集进行压缩处理。文献16】同样使用了基于规则的方法来处理关联数据集中
20、的语义冗余内容，但是与前面两种方法的不同在于，这种压缩方案支持普遍的关联数据集，该方法通过对关联数据进行分析并提取规则，利用规则推理方法去除数据集中的冗余三元组，同时原本的语义信息也没有损失。另外，由于关联数据集中大部分的内容都与本体17】中2万方数据武汉科技大学硕士学位论文定义的属性相关，本体压缩【18】也属于对语义冗余信息的处理。在序列化层次上，RDF数据以一系列的比特值内容的形式表达，通常以预先定义的语法处理成文本格式或者二进制文件进行存储，例如RDFXML19】，NTriples20或者一些复杂的压缩格式。在这个层次上的冗余内容主要有字符长度冗余和语法冗余。对于字符长度冗余内容的处理，
21、主要是通过对关联数据集中表示一个资源所需要的平均字符长度进行处理，在整体上减少关联数据集的文件体积。一般是通过构建字典为RDF三元组的URI标识分配更简短的标识，从而达到压缩的目的。而对于语法冗余内容的处理，主要的思路是通过以不同的方式对关联数据的存储结构进行表达，对关联数据采用更简洁的数据结构【2l】来表示，从而完成压缩的需求。最初文献【22】提出了对关联数据进行压缩的一些基础方案，例如可以利用一般的文件压缩技术如LZMA23】和bizp224】对关联数据进行压缩，这些压缩技术修改了关联数据的文件结构，能够明显的缩小文件体积，其次他们还提出字典压缩技术与图压缩技术相结合的压缩方案，但并没有给
22、出一个具体的实验。同年，Atre等人【25提出了BitMat方案，BitMat用一种紧凑的比特矩阵结构来存储关联数据集，并且支持在压缩数据集上直接进行查询操作，但是这种方案的扩展性不高，且采用的压缩技术比较简单。文献2627】还介绍了一种新的关联数据压缩方案HDT，HDT将关联数据中的信息分解成为三个部分：第一部分称为头部(Header)，头部保存了描述整个数据集的逻辑和物理元数据，例如数据集的来源、编辑信息以及数据集的一些统计信息等；第二部分称为字典(Dictionary)，字典部分主要是将数据集中的资源映射成一个唯一的ID；第三部分称为三元组(Triples)，这一部分先将数据集中的三元组
23、ID化，然后根据三元组的主语信息将三元组分组，最后对这些三元组进行压缩，它保存了数据集的底层结构，同时避免了数据集中比较长的以及重复的资源描述。HDT是一种比较有效的压缩方案，并且经过HDT压缩后的文件还可以通过bzip2等文件压缩技术再次压缩。受HDT方案的启发，很多基于HDT方案的压缩技术也被提出，如HDTFoQt2引、WaterFowl291、HDTH【30】。大型关联数据的压缩一般比较耗时，于是Urbani等人【3l】将字典编码技术与MapReduce32】相结合，采用分布式方案快速的压缩大型数据集。文献33也同样将HDT与MapReduce结合在一起，加快了HDT的压缩速度。目前主流
24、的压缩方法都是基于序列化层次的，因为数据模型层次只是去除语义层次的冗余三元组，而随着关联数据发布规范的不断推进，以后发布的数据集也会越来越规范化，语义冗余的减少使这个层次上的压缩能达到的效果也会越来越低。而序列化层次压缩是从数据本身的数据结构优化入手，不会受限于RDF数据的语义规则，因此可以保持更好的压缩率和通用性。因此，本文主要研究关联数据集的3万方数据武汉科技大学硕士学位论文序列化层次压缩。13本文的主要工作本文主要研究关联数据的序列化层次压缩，基于字典映射以及关系三维矩阵，通过分析现有的序列化压缩方法的思路，提出了基于分级树形索引的压缩模型，主要工作包括以下几个方面：对现有的序列化层次的
25、RDF数据压缩方法进行分析，从关系三维矩阵的分布和编码方面对问题进行分析并提出解决思路。对数据集进行压缩构建字典并映射处理，通过将原有的URI标识转化为简短的ID进行表示。基于生成的ID三元组集设计相应的三维矩阵，利用矩阵结构对ID三元组内的单次表达实现对语法冗余信息的压缩处理，构建基于分级树形索引的压缩模型，完成对关系三维矩阵存储结构冗余信息的压缩处理。本文在压缩后的序列化结果上提出了分层的数据结构，该结构便于结点的匹配检索，保持了逻辑结构的形象表达。同时结合关联数据的查询模式对其进行匹配分析。结合实验结果和三维矩阵分布图，分析不同空间分布对该压缩模型压缩率和查询效率的影响因素。14本文的结
26、构安排本文共分为五个章节，各章节的主要内容如下：第一章是本文的绪论，介绍了关联数据的冗余性问题，并分析了解决冗余问题对于关联数据的重要性，对现有的压缩方法进行分类，然后在数据表达的两个层次上压缩处理技术进行了分析比较，在此基础上，概括了本研究的主要工作内容。第二章介绍了与本文研究相关的基础理论和相关知识。介绍了RDF数据模型以及关联数据压缩的分类，最后介绍关联数据表达的方法，并且对不同层次上的压缩处理方案进行分析和总结。第三章对序列化层次的不同压缩方案进行分析和比较，从关系三维矩阵的角度提出对RDF三元组数据集的压缩思路。详细分析了压缩模型的构建过程以及减少冗余内容的思路，在后面提出了压缩模型
27、的序列化结果的分层存储结构，通过该分层存储结构可以便利地对三元组进行检索。然后根据这个结构分析了该压缩模型在基本的查询模式下的匹配情况。4)，)l234，k，-，k万方数据武汉科技大学硕士学位论文第四章设计了压缩率和查询效率的对比实验，根据实验结果，分析了本文提出的压缩模型的优势以及瓶颈。首先介绍了实验所采用的数据集，然后根据已有的方案做了压缩率和查询效率的对比，并根据实验结果做了详细的分析。第五章为总结和展望。总结了本文所做的工作，对本文的不足和可以改进的方面进行了分析，并对将来的研究工作进行了展望。5万方数据武汉科技大学硕士学位论文第2章基本理论与相关知识21 RDF数据模型RDF(Res
28、ourceDescriptionFramework)是由W3C所提议的一种用于构建和处理元数据的技术标准，目的是定义一种通用的用于描述资源以及资源之间的关系的机制，其表述的资源类型可以是任何可描述的内容，包括文件、人物、实体对象以及抽象的概念等。RDF通过表述资源的结构信息，使网络资源不仅仅只是展示给人阅读和处理的内容，而是更进一步，使机器和应用可以理解资源，从而对其中包含的信息进行处理。RDF使用统一资源标识符(URI)等方式来对资源进行标识，在RDF中，资源是以陈述的形式进行表示，陈述的内容由资源、属性以及属性值三部分构成，属性部分描述资源之间存在的关系，或者是资源本身的属性和特征；属性值
29、则表示这个资源在这个属性上所表述的值。因此RDF可以将资源表述为一个结构的三元组，其中主语(subject)用于描述资源，谓语(predicate)用于描述资源的属性，宾语(object)用于描述属性所对应的属性值。URI标识可以用来表述三个部分，而空白结点可以对主语和宾语进行表述，文字描述例如数字或者日期只能对宾语进行标识。22关联数据压缩关联数据的主要表示方式是RDF数据模型，因此对关联数据的压缩可以说是对数据集中的RDF三元组数据冗余的处理。从数据模型上来说，关联数据集本质上是由不同的三元组集构成的RDF图的集合。而为了便于传输以及对RDF数据集进行查询操作，数据集还需要通过序列化处理转
30、化为便于读取操作的比特序列流，该操作对应了RDF数据的序列化层表示。在序列化层次上， RDF三元组一般使用预设的语法格式转化为对应的文本格式或二进制数值。RDF三元组数据的冗余信息同时存在于这两个层次上，根据对数据冗余处理的着重点的不同进行分析，对于关联数据压缩可以作如表21的划分。6万方数据武汉科技大学硕士学位论文表21 RDF数据冗余处理层次类型 语义压缩 语法结构压缩 字符长度压缩数据模型层次 T】nle序列化层次 True Tnle221数据模型层次压缩数据模型是数据描述在现实世界的抽象表示。因此，在数据模型层次上，关联数据集的大小可以通过RDF三元组的数目来计算。对于关联数据集而言，
31、在语义信息没有损失的前提下，如果可以使用更少的RDF三元组对关联数据集进行表示的话，由此判断关联数据集在数据模型层次上存在冗余信息，冗余的形式为语义表述中多余的RDF三元组。因此，通过对关联数据集进行处理，减少数据集表述所需的RDF三元组数目，便可以实现对关联数据集的语义压缩。语义压缩主要依赖对关联数据的规则推理，通过对数据集中的语义判断来判别多余的RDF三元组，根据判断结果缩减三元组数量，完成对关联数据的压缩。例如，对关联数据集中以空白结点作为主语标识的三元组而言，由于空白结点在RDF语义中只是作为一种占位符存在，并没有实际的语义表达，因此如果有空白结点陈述的信息与数据集中其他的结点所陈述的
32、信息相同，可以推断包含这些空白结点的RDF三元组是冗余三元组，便可以通过语义压缩去除34-35】。通常情况下，语义压缩需要为压缩数据集提供附加规则，保证可以重新生成被移除的RDF三元组，完成对压缩数据集的解压。由于语义压缩只是在数据模型上对RDF三元组的数量进行了压缩，数据的结构并没有变化，因此可以在语义压缩的基础上进行序列化的压缩处理，获得更高的压缩效果。222序列化层次压缩为了便于RDF数据的传输与查询操作，关联数据需要转换为可以存储、查询以及传输的序列化结构。在序列化层次，RDF三元组数据是以文本序列或者二进制比特序列的形式存在的，关联数据集的大小取决于序列表达单位的数量。对于同一组RD
33、F三元组，相较于当前的线型序列，如果可以通过不同处理以更少的序列值个数进行表达的话，那么当前的线性序列值便存在冗余信息，而获得新序列值的处理方法即是对线性序列值的压缩。对于关联数据集的线性序列值，可以通过字节数以及资源个数来计算数据集的大小。用F表示一个关联数据集的大小，R表示关联数据集中资源表达所需要的平7万方数据武汉科技大学硕士学位论文均字节数，N表示所有资源出现的次数，数据集的大小可以用如下公式计算：F=NR (21)对于关联数据集而言，文件的大小由N和R共同决定。根据N、R两个因素的划分，关联数据集的线性序列值可以分为两种压缩方式：l、语法结构压缩对于关联数据集的线性序列值而言，如果存
34、在另一种语法结构，使序列值中同一个资源的重复出现次数大幅度减少，那么线性序列值对资源表述所需要的位数也会大幅减少。根据公式2一l计算，可以实现对关联数据集的语法结构压缩。例如，当使用NTriples语法对RDF三元组进行表示时，相较于其他使用命名空间的语法而言，很多RDF三元组会多次表达，导致每个资源需要占用更多的字节数。相较于NTriples语法，使用命名空间的语法实现了对关联数据集的语法结构压缩。2、字符长度压缩通过分析RDF三元组的结构可以发现，在直接使用三元组方式对关联数据进行表达时，每个三元组的主语、谓语以及宾语的标识都需要使用较长的字符串进行表示。分析公式21可知，如果可以对各种标
35、识的表达长度进行缩减的话，那么就可以实现关联数据集体积的减小，这种处理方式叫做字符长度压缩。HDT中基于字典映射标识的方法就是对字符长度的压缩，通过将标识按照一定排列映射成对应的整数ID，可以显著地减少关联数据集的线性序列值长度。同时，字典文件中每个标识只存储一次，同时也实现了对语法结构的压缩。可以得到较好的压缩率。相较于数据模型层次的压缩，序列化层次的压缩是基于序列值的语法结构和字符长度进行缩减，对关联数据集的压缩效率更加明显。本文提出的压缩模型是先从关联数据集构建字典，然后再对线性序列值构建紧凑的语法结构，实现语法结构和字符长度上的压缩。23图模型表示方法RDF三元组设计的初衷是通过对资源
36、属性进行表述，以此推理其中的关系，从而建立关联数据集，以机器便于解析的方式进行自动化处理。因此，并不能很好地支持可视化的数据集构成分析以及可视化展示。随着关联数据集体积的增加，在巨大数量级的RDF三元组中，以NTriples等方式表示的内容在人为阅读和分析时会变得极其复杂和低效。考虑到使用者分析数据及特性的实际需求，人们提出了基于8万方数据武汉科技大学硕士学位论文图模型的RDF表示方法f36371。通过21章节中对RDF三元组的分析知道，RDF的资源、属性以及属性值是相互连接并对应的，考虑到图的数据结构，可以将对资源的属性描述用由结点和边构成的有向图进行表示。其中，结点由主语元素和宾语元素构成
37、，而有向边由谓语元素构成。用V表示RDF图中的结点集，E表示有向边集，那么一个RDF数据集可以表示为G=(V，E)。例如，有如下RDF三元组：对于这个三元组集，用圆形结点表示主语元素和谓语元素，用带标签的有向箭头表示谓语元素，那么可以把这个RDF三元组集表示为如图21所示的有向图的形式：图21三元组的图模式表示在图中，结点A作为起始节点表示，属性值C和D作为结束结点表示，属性Pl、P2在图中以标记的有向边进行表示，从图的结构中可以很清晰的看出资源之间的联系及属性分类。例如资源B的P2属性同时具有C和D两种属性值，而资源B也是与、建立关联的枢纽所在。尽管有向图表达方法可以很方便地展示关联数据之间
38、的资源关系和属性，但图的数据结构决定了这种表达方式有很高的时间复杂度和空间复杂度，对数量级不大的小数据集的表述需求可以很好的支持，但在面临包含百万甚至亿级数量的三元组数据集的时候，更多数量的资源结点以及它们之间的关系所构成的边会使图的结构变得十分复杂。从l。l章节的介绍中可以看出，实际的数据集的体积在飞快的增加，9万方数据武汉科技大学硕士学位论文基于图模式的RDF表示方法也越来越力不从心，因此，基于关系三维矩阵的表示方法被提出，从而解决这个问题。24关系三维矩阵表示方法通过分析RDF数据模型的组成结构，文献38】提出了基于关系三维矩阵的RDF表示方法，利用这种表示方法，不仅能像图结构一样在逻辑
39、上对关联数据内资源间的联系进行清晰的表达，同时还可以实现对关联数据集的序列化层次的压缩处理。对于以三元组表示的RDF数据，通过对原本数据集中不同的主语元素、谓语元素以及宾语元素分配唯一的数字D，可以构建字符串映射到数字ID的字典文件，利用这个字典文件，也可以将D反过来还原成对应的字符串。通过对RDF三元组进行字典化映射处理，可以得到与RDF三元组对应的ID三元组。例如，对于23章节中的RDF三元组集，处理的过程如下：表22 RDF三元组映射字典主语&宾语 lB主语 2A2C宾语3D1_Pl谓语2P2在字典中，对于B结点这种主语元素和宾语元素中共同的构成部分表达了资源之间的关联关系，所以单独进行
40、分块编号是很有必要的。通过对RDF三元组进行逐一映射可以得到对应的ID三元组集。在上述的处理结果中，ID并不是全局唯一的，而是有所重叠，这跟它们本身的角色有关。例如值2就同时分配给了谓语元素P2和宾语元素C。通过映射处理后，原本RDF三元组中的长字符串转换成了整数，而转换得到的三元组(S，PO)可以看作一个三维空间里的(x，y，z)坐标点，基于这一思想，利用X轴的坐标表示主语元素S的ID，利用y轴的坐标表示谓语元素P的10万方数据武汉科技大学硕士学位论文ID，利用Z轴的坐标表示宾语元素O的D，可以构建起对应RDF数据集的三维空间矩阵中的点集。通过这种方法可以很直观地对大量的RDF三元组进行表达
41、，同时利用对资源表达需要的字符长度的压缩，节约了很多的存储空间。不仅如此，转换成关系三维矩阵中坐标点的三元组集同时也在存储形式上与原本的三元组保持格式一致，而在这一表示方法的基础上，可以通过对D三元组存储结构的不同组织方式实现压缩。本文就是基于对RDF的关系三维矩阵表达方法进行序列化层次的压缩。25本章小结本章首先介绍了RDF数据模型的概念，把RDF数据集的压缩层面归类为数据模型层面和序列化层面，并根据不同的冗余处理对序列化层次的压缩做了详细划分。然后介绍了RDF数据集可视化以及便于操作处理的两种表示方法，分析其构建思路以及处理数据时的利弊，对关系三维矩阵表示方式进行了介绍，并提出本文的压缩方
42、法就是基于关系三维矩阵表达方式的序列化压缩。万方数据武汉科技大学硕士学位论文第3章基于分级树形索引的数据压缩31问题的提出与分析目前关联数据在序列化层次上的压缩主要有基于字符长度处理与基于语法结构处理的两种思路。基于字符长度的压缩思路主要是通过对RDF数据模型中的URI标识等的平均表示长度进行处理，从而实现整个数据集的压缩。目前在这方面比较成熟的方案都是以字典化的思路来对构成RDF三元组的主语、谓语和宾语的URI字符串或常量进行映射处理，通过将重复的URI字符等映射为唯一的整数D标识，形成和RDF三元组逐一对应的ID三元组组成的数据集，从而显著的减少因为U砒字符长度问题所造成的冗余信息。基于语
43、法结构的冗余处理思路主要是通过修改数据的存储结构来实现压缩，因此可以在基于字符长度的压缩之后进行进一步压缩。现有的压缩方案的区别主要在于对字典化等转换之后的数据的不同处理方式上。HDT(Header-Dictionary-Triple)中使用的BitMap方案26-27】通过提取字典化后生成的ID三元组之间的关联规则，结合线性序列值以及线性比特预测位设计存储结构，在字典化的m三元组数据集上做更进一步的压缩。对于这种语法结构压缩思路，很多冗余的数据项都会被去除，因此压缩率比较高。但是由于数据的结构的改变，这种方案最终获得的压缩数据的主语、谓语以及宾语之间的关联关系比较隐晦，对查询的支持并不理想。
44、另一种关联数据语法结构压缩的思路则是从关系三维矩阵的方面着手。这种压缩方法在数据结构上将三元组看作三维矩阵中的点进行处理，基于字典的映射以及ID三元组的表述，很好地保持了原有三元组组成部分之间原本所存在的语义关联关系，这种存储结构可以很方便的实现查询操作。但是，为了维护矩阵的存储结构，一些相互之间没有逻辑关联关系的主语、谓语和宾语的部分也需要占用存储空间来表述。如果当关联数据集的规模不断增加的时候，这个由关联数据集所构成的稀疏矩阵里的冗余内容也在持续增长，稀疏三维矩阵里大量冗余信息的存在是这种存储结构在压缩率上的瓶颈所在。BitMat方案25】采用了紧凑的比特矩阵结构，但是这种方法对于稀疏矩阵
45、中的冗余内容去除的效率并不高。而K2triple39】方法则是通过将关联数据集按照谓词拆分成多个稀疏二维矩阵进行压缩，相较于BitMat具有较好的压缩效果。但是K2。triple所借用的结构最初设计的初衷是对二维结构的网络图进行压缩存储，在抽取谓词对关系三维矩阵表示的RDF三元组构建稀疏二维矩阵时，会造成一些存储空间的浪费。本文最初的方案是基于表述三维空间形体的八叉树结构建立数据压缩模型。对12万方数据武汉科技大学硕士学位论文于三维矩阵而言，序列化层次的冗余信息主要在于为了维持矩阵结构对空白内容的存储。八叉树最初设计的初衷是用于对三维物体进行表述【40】，其划分的思路是把一个立方体划分为八个小立方体，递归地分割这些小立方体直到设定的最下层，或者在不存在实际内容的立方体停止分割。利用这一特性对三维矩阵进行存储可以有效的减少没有实际内容的矩阵元素对存储空间的浪费。但是为了保存数据的树形索引也需要占用一些存储空间，不能得