大规模半结构化数据管理关键算法研究与实证

《大规模半结构化数据管理关键算法研究与实证》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、声明本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得云南大学或其他教育机构的学位或证明而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。研究生签名：日期：∞＆每罗论文使用和授权说明本人完全了解云南大学有关保留、使用学位论文的规定，即：学校有权保留并向国家有关部门或机构送交学位论文和论文电子版；允许论文被查阅或借阅；学校可以公布论文的全部或部分

2、内容，可以采用影印、缩印或其他复制手段保存论文；授权学校将学位论文的全部或部分内容编入有关数据库进行检索。(保密的论文在解密后应遵循此规定)研究生签名：煎!导师签名：日期：型堑g摘要lIIIIIIIIIIIHIIIIMIIJY2370745随着互联网技术的飞速发展，传统的结构化数据已经无法满足人们对信息处理的要求。尤其是在云计算和物联网高速发展的今天，对管理半结构化数据、大规模信息处理等领域的研究受到越来越多的关注。由于半结构化数据模型既能描述半结构化数据又能描述结构化数据，且具有灵活易扩展的存储结构，其已被许多系

3、统和应用作为公共数据模型，被广泛地用于异构数据量大的使用场景中。如今，几乎所有行业都制订了描述和共享本领域数据的半结构化数据模型应用标准。此外，由于半结构化数据模型具有易于描述结构、易于校验、易于展现等特点，许多原本是以非结构化方式进行存储的数据，也通过半结构化数据模型进行描述并存储。因此，如何对大规模半结构化数据进行有效的管理，在学术界是一个重要的理论研究课题，而在工业界又是一项具有广阔应用前景的技术。本文以XML为代表，探讨了大规模半结构化数据管理中的关键问题一一模式提取、节点编码、索引与查询处理等研究课题。主

4、要研究成果与创新点如下：(1)针对现有基于正则表达式的模式提取方法的不足之处，本文根据XMLSchema规范中元素内容模型的特点，提出了XTree算法，该算法可以快速、准确地并发提取多个大规模(GB级)XML文档的结构。该算法和基于正则表达式的算法最显著的区别在于，XTree对于元素内容模型的提取加入了对元素内容模型是否有序的区分，降低了算法的时间复杂度和空间复杂度。(2)针对现有半结构化数据节点编码方案的不足之处，本研究提出了D2编码方案，该算法在静态编码和动态编码中都体现出良好的性能，且易于二进制串行化和反串行

5、化，具有较高的实用价值。和其他半结构化数据节点编码方案相比，D2编码最显著的特点在于，突破了传统的以整数作为层标识的限制，采用二进制真分数作为层标识，由于真分数的取值区间是无穷的，所以可以保证在任意位置插入节点都存在有效的编码。(3)本研究综合考虑了目前已有的关系型数据库和大规模半结构化数据的索引技术的优缺点，提出一套完善的索引方案～一D2．Index索引策略，能够支持高效的查询处理。它并不只使用了一种单一的索引技术，而是参考和借鉴摘要了多种技术，如节点编码索引、结构索引和倒排索引等。D2．Index索引策略的最显

6、著之处在于，它的索引文件包括了主索引、路径辅助索引和值辅助索引，这三种索引都采用分块存储的方式提高索引的查找和修改效率。此外，由于是基于D2编码方案的，所以D2．Index索引策略可以有效地支持节点的动态更新。(4)根据目前对于大规模半结构化数据查询处理的研究，本文提出一种以D2．Index索引策略为基础，基于XPath表达式的CAS查询处理。这种查询处理最大的特点在于，将输入的合法CAS语句拆分为多个BXCAS语句，再对拆分的语句按顺序进行处理，根据D2一Index策略中的路径和值辅助索引，获取符合查询条件的节点

7、的D2物理编码，再从主索引中获知其在源数据中的位置信息，最终以异步的方式输出结果。关键字：大规模半结构化数据；模式提取；节点编码；索引；查询处理IIAbstractWiththerapiddevelopmentofIntemettechnology,traditionalstructureddatahavebeenunabletomeetthedemandsforinformationprocessing．Nowwiththerapiddevelopmentofcloudcomputingandphysicalne

8、tworking，thestudyonmanagementofsemi-structured，largeinformationprocessandotherareashaveattractedmoreandmoreattention，especiallythestudyonprocessofsemi—structureddata．Semi—structure