XCube的计算和查询

论文摘要

随着B2B等应用的普及,越来越多的数据以XML文档的形式出现,如何对XML文档中的数据进行联机分析引起了研究工作者的关注。传统的做法是先将XML中数据转换为关系的元组,再进行计算。本文中,我们通过直接对XML文档进行操作,避免了数据转换过程,提高了运算效率。XCube是关于XML的一个立方体结构,在实际应用过程中,当输入数据量太大时,受内存限制,无法完成运算。若把数据分批输入进行运算,则会产生许多重复的中间结果,要形成最终结果需从磁盘中把这些中间结果读入内存再进行大量的合并工作。因为涉及磁盘的读操作及大量的合并操作,使运算时间增加好几个数量级。通过分析和实验,我们对XCube算法进行了改进,提出了“分批输入分次计算”的方法。当数据量很大时,按照新改进的方法进行分批输入计算时,我们只生成最终结果的分支,对于中间结果的分支不予计算,避免了对中间结果中某些分支的合并过程。通过对数据进行分次计算的方法,生成剩余分支,使运算顺利完成。因为运算中没有涉及到从磁盘中读中间结果进行分支合并的过程,所以提高了运算效率。Bloom Filter(布隆过滤器)是1970年由Bloom提出的,它利用hash table,通过hash函数将元素映射成bit array中一个点。当检索时,只要查看相应点的值是否为1就可知这个元素是否在集合中。为了增加准确度,Bloom Filter中可以利用多个hash函数。通过对相关查询算法研究,我们发现XCube的点查询为一个从根节点到叶子节点的路径匹配过程,于是我们按照Bloom Filter的思想提出了一个新的压缩查询算法：BXCube算法。把XCube算法中产生的每条从根节点到叶子节点的路径作为整体,通过多个(两个或三个)hash函数进行计算,分别产生多个hash值。我们只存储由hash值、度量值及Tag域构成的结构,称为Bloom元组。相对于存储整条路径,存储Bloom元组,节省了存储空间并对机密数据提供了一定的安全保障。路径长度越长,效果越明显,更适用于高维数据。由于hash函数本身的问题,当数据量太大时,不可避免的会出现hash冲突。为了消除因为hash冲突而使查询结果错误的问题,我们设计了一个过滤结构：过滤器表。在运算时,把同一棵子树的所有路径经过运算,放入过滤器表中,经排序后,若相邻的临时Bloom元组hash值相同,而度量值不同,则需要把这两个路径字符串经过一个新的hash函数进行hash计算,当产生的hash值可区分时,把第一个路径字符串产生的hash值、两条路径对应的度量值及所用的hash函数ID放入冲突表中,而在查询表中,只存储一个Bloom元组,其Tag域的值指明如何解决冲突。若相邻的三个元组间存在冲突时(概率极小),则通过路径表处理。当冲突检测完后,把结果放在查询表中,同时在索引表中记录该棵子树产生的Bloom元组在查询表中的位置。当查询时,首先通过查询路径的根节点的值在索引表中查找查询范围。若值在索引表中,则可通过查询得到在查询表中的查询范围。把整条查询路径作为一个整体经过相应hash函数计算,生成临时元组。把临时元组在查询范围内进行折半查找,返回查询结果。因为与Dwarf结构类似,都是树形结构,所以我们和Dwarf算法进行了比较。实验结果表明BXCube算法在存储空间和查询响应时间方面都优于Dwarf算法。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 课题背景
• 1.2 研究内容及意义
• 1.3 论文组织结构
• 第二章 联机分析和XML
• 2.1 联机分析
• 2.2 数据立方体
• 2.3 XML
• 2.4 XOLAP
• 第三章 算法分析和设计
• 3.1 XCube算法及实现
• 3.2 BXCube算法
• 第四章 实验分析
• 4.1 实验数据集
• 4.2 XCube算法
• 4.3 BXCube算法
• 第五章 总结和展望
• 5.1 本文总结
• 5.2 工作展望
• 参考文献
• 致谢
• 攻读硕士学位期间论文发表及科研情况