概率XML文档的查询研究

摘要

随着数据采集和处理技术的不断发展和进步，使得人们对不确定性数据的认识逐步加深，对不确定性的概率数据的研究也获得了广大科研工作者的更加广泛的关注。XML是由W3C所发布的一种标记语言。XML所具有的灵活特性非常适合描述、表示、存储，不确定性数据，利用XML表示不确定性数据正越来越多的应用于各个不同的领域中，进而导致概率XML文档的数量呈现出急剧增长的态势。使用传统的XML聚类和查询技术处理海量概率XML文档所造成的时空消耗令人无法接受。尽管针对不确定XML聚类和查询的技术的研究已经有很多，但仍有一些方面需要进行改进和完善。
　　针对概率XML文档的查询研究，本文深入研究了当前已提出的方案，分析了其中存在的问题，并对这些问题提出了针对性的改进策略。本文所做的工作有:
　　第一，直接聚类XML文档精度较高但存在时空消耗大等缺点，利用聚类DTD文档的时空消耗较小的优势，提出了基于DTD的XML文档聚类方法WSDTD。DTD文档可以从一定程度上反应出XML文档的内容和结构，通过聚类XML文档对应的DTD间接聚类XML文档。定义DTD文档对应的树形结构的结构相似度和语义相似度，用K-Means聚类算法对DTD文档树进行聚类，达到对XML文档聚类的目的，从而有效地缩小了查询范围，为海量XML文档查询奠定基础。
　　第二，针对概率XML文档的特点，本文设计了概率XML文档的查询算法pTwigList。在TwigList算法的基础上，加入了Top-K关键字查询思想，进行了三次阈值过滤，对存在概率较低或非法的查询结果予以舍弃，形成了pTwigList算法。并辅以改进的区域编码，这样就能达到查询概率XML文档的目的。
　　第三，通过仿真实验验证本文所提出WSDTD和pTwigList的有效性。实验采取了查询时间来衡量查询效率。仿真实验分成两个部分，第一部分用来验证先使用WSDTD算法聚类，后使用pTwigList进行查询的时间消耗小于直接对海量XML文档进行pTwigList查询。第二部分用来验证pTwigList算法在不同的测试用例下、不同的K值下、不同的文件大小下的有效性。通过与其他算法的结果对比，验证方法有效减少了查询时间。结果表明，本文提出的方案减少了概率XML查询时间。

目录

声明

摘要

第1章 绪论

1．1 研究背景及意义

1．1．1 不确定性数据的产生

1．1．2 XML表示不确定性数据的优势

1．1．3 研究背景和意义

1．2 国内外研究现状

1．2．1 XML聚类技术研究现状

1．2．2 XML索引技术研究现状

1．2．3 XML查询技术研究现状

1．3 研究内容

1．4 论文结构

第2章 XML文档和其他相关技术分析

2．1 概率XML文档

2．2 语义相似度计算工具JWS

2．3 聚类分析

2．3．1 样本距离

2．3．2 样本相似度系数

2．3．3 常用聚类方法

2．4 本章小结

第3章 基于DTD的XML文档聚类方法WSDTD

3．1 通过DTD文档生成DTD树

3．2 DTD树之间的相似度

3．2．1 DTD标签语义相似度计算

3．2．2 DTD树结构相似度计算

3．2．3 根据内容相似度和结构相似度进行聚类

3．3 本章小结

第4章 概率XML文档查询

4．1 DTD文档编码

4．2 概率XML文档编码

4．3 pTwigList算法

4．3．1 pTwigList-Construct算法

4．3．2 pTwigList-Enumerate算法

4．3．3 应用pTwigList算法进行查询

4．4 本章小结

第5章 实验结果分析

5．1 数据预处理

5．2 算法效率度量标准

5．3 仿真实验内容及结果分析

5．4 本章小结

结论

参考文献

攻读硕士学位期间发表的论文和取得的科研成果

致谢