XML非完全结构查询处理中若干关键技术的研究

论文摘要

随着Internet的发展和异构信息源集成技术以及存储技术的进步，网络中涌现出大量半结构化数据资源。XML由于其所具有的自描述性、灵活的数据结构以及丰富的数据表示能力等特点，逐渐成为数据表示、存储和交换标准之一。近年来，XML非完全结构查询处理技术作为有效管理XML文档的关键技术之一，引起越来越多研究人员的关注。 XML非完全结构查询（Non-fully Structured Query,NFS Query）是指满足用户在缺乏完整的XML文档结构信息情况下的查询需求。NFS查询是近两年出现的XML查询技术，其主要面向缺少完整的结构信息说明以及异构环境下的查询需求。在实际中，特别是在Internet和Intranet上，大部分XML文档缺少结构说明或存在异构现象，这使得NFS查询有着广泛的应用前景。本文就XML非完全结构查询处理技术中的有意义的NFS查询结果判断技术和基于内容的查询结果聚类技术进行了深入研究。 有意义的NFS查询结果判断是NFS查询处理中非常重要的一环，现有的判断方法，如XSEarch中的Interconnection Relationship和Timber中MLCA，都是从一个特定的角度来设计判断标准，缺乏一个准确和全面的定义，这使得它们只能适用于特定的XML文档。另外，现有方法无法适应于大规模XML文档，如XSEarch的索引建立时间和Timber的查询时间在大规模XML文档下远远超出用户的容忍程度。 本文提出了一种基于模式和实体概念的有意义的NFS查询结果判断模型一PE模型。PE模型从系统角度出发定义了一种用户普遍接受的判断方法，与具体的等价模式和等价查询项的判断方法无关，具有可扩展性。基于PE判断模型，提出一种具体的基于结构相似性的等价模式判断方法，并给出了一个判断规则。为了提高NFS查询的执行效率，设计了模式索引PE和增强的倒排索引I2P，提出一种高效的NFS查询算法，它们不仅可以支持高效的路径查询和关键字查询，而且可以有效地支持本文提出PE模型，并有效地利用了现有XML数据库系统中的索引资源，适用于大部分XML编码方案。实验表明，本文方法的效率和准确率要远远高于XSEarch和Timber系统，适用于大规模XML文档。 NFS查询为非精确查询，在XML文档规模较大的情况下，NFS查询往往返回大量结果。而以文档为中心的XML文档节点包含了大量的文本信息，为了方便用户快速定位所需信息，通常需要对结果按照内容进行聚类。文档聚类是实现这一目的的有效技术之一。基于概率模型的聚类方法具有高维数据适用性和簇可

论文目录

• 独创性声明
• 学位论文版权使用授权书
• 摘要
• ABSTRACT
• 目录
• 第一章 绪论
• 1.1 研究背景
• 1.2 本文工作
• 1.2.1 研究动机
• 1.2.2 研究内容
• 1.2.3 本文组织结构
• 第二章 XML查询处理技术概述
• 2.1 引言
• 2.2 XML文档模型
• 2.2.1 对象交换模型（OEM）
• 2.2.2 文档对象模型（DOM）
• 2.3 完全结构查询模型
• 2.3.1 定义
• 2.3.2 查询模型
• 2.3.3 模型比较
• 2.4 非完全结构查询模型
• 2.4.1 定义
• 2.4.2 查询模型
• 2.4.2.1 XML文档检索
• 2.4.2.2 FS查询扩展
• 2.4.3 模型比较
• 2.5 XML查询处理关键技术
• 2.5.1 XML文档编码方法
• 2.5.1.1 基于区间的编码
• 2.5.1.2 基于路径的编码
• 2.5.2 结构索引技术
• 2.5.3 倒排索引技术
• 2.5.4 有意义的NFS查询结果判断
• 2.6 小结
• 第三章 基于模式和实体的NFS查询处理方法
• 3.1 引言
• 3.1.1 相关概念和模型
• 3.1.2 NFS查询模型
• 3.1.3 问题提出
• 3.2 PE判断模型
• 3.2.1 模式和实体
• 3.2.2 PE规则
• 3.3 基于PE模型的NFS查询方法
• 3.3.1 XML编码
• 3.3.2 等价模式和等价查询项
• 3.3.3 PE索引
• 3.3.4 12P倒排索引
• 3.3.5 判别方法
• 3.4 算法设计
• 3.4.1 PE索引和I2P索引创建算法
• 3.4.2 NFS查询执行算法
• 3.5 实验分析
• 3.5.1 实验设计
• 3.5.2 实验结果
• 3.5.3 性能分析和比较
• 3.6 小结
• 第四章 文档聚类技术概述
• 4.1 引言
• 4.2 文档特征降维技术
• 4.2.1 特征选取技术
• 4.2.2 基于概念的降维技术
• 4.3 基于传统聚类技术的文档聚类方法
• 4.3.1 基于相似性的聚类方法
• 4.3.2 基于模型的聚类方法
• 4.3.3 基于划分的聚类方法
• 4.3.4 基于层次的聚类方法
• 4.4 面向文档特性的聚类方法
• 4.4.1 潜在语义分析
• 4.4.2 基于信息论的文档聚类方法
• 4.4.3 双向聚类方法
• 4.5 聚类质量评价方法
• 4.6 小结
• 第五章 基于模型的非偏斜文档聚类方法
• 5.1 引言
• 5.2 相关工作
• 5.2.1 基于多项式分布的硬聚类
• 5.2.2 基于平衡约束的聚类方法
• 5.3 聚类偏斜的分析
• 5.3.1 相关概念与定义
• 5.3.2 聚类偏斜产生的原因
• 5.4 MMPClust聚类方法
• 5.4.1 基于内容特性的簇模型
• 5.4.2 估计样本选取
• 5.4.3 MMPClust算法
• 5.5 实验分析
• 5.5.1 数据集
• 5.5.2 实验方法与评价方法
• 5.5.3 实验结果与分析
• 5.6 小结
• 第六章 基于信息论的潜在概念获取与文档聚类方法
• 6.1 引言
• 6.2 相关工作
• 6.3 模型提出
• 6.3.1 词、潜在概念、文档和主题的关系
• 6.3.2 模型描述
• 6.4 模型求解
• 6.4.1 给定β下目标函数求解
• 6.4.2 潜在概念个数确定
• 6.4.3 算法设计
• 6.5 实验分析
• 6.5.1 数据集和实验方法
• 6.5.2 性能分析
• 6.6 小结
• 第七章 总结与展望
• 7.1 总结
• 7.2 进一步工作
• 参考文献
• 致谢
• 攻博期间发表的文章
• 攻博期间参加和完成的科研项目
• 作者简介