kFilter：基于关键字查询的XML流过滤系统

论文摘要

随着互联网技术的飞速发展和XML逐渐成为数据存储和交换的标准,出现了很多与XML数据流紧密相关的应用,例如,SDI（Selective Dissemination ofInformation）。针对这些问题,人们提出很多解决方案,比较有代表性的是基于自动机的过滤方法和基于索引的过滤方法。当前几乎所有的XML数据流处理方面的研究都是基于XPath或XQuery的,这主要会带来两个问题:首先,用户必须熟悉一门复杂的查询语言,而这一点对很多用户,尤其是初级用户是很不切实际的;其次,用户还必须知道流过来的数据的结构（或模式,schema）,这样他们才能够写出查询来。针对存在的问题,文章[20]首先提出了在XML数据流上使用关键字查询的方式。关键字查询是一种对用户有好的查询方式,并且被广泛地应用于信息检索等领域。它的最大优点在于其简单性。对XML流数据用关键字来进行查询,用户就不必掌握一种查询语言,也不需要知道流数据的模式。尽管[20]中提出了一种基于栈的Lookup算法来对XML数据流进行关键字查询,但是其算法并不是高效的,并且该算法只是针对单个查询而言的,文章中并没有提出如何对多个查询进行过滤的方法,这与现实中流处理系统往往拥有大量的用户查询不符合。本文提出了最右包含边界的概念,并在此基础上提出了处理单个查询的算法XVirtualStack（XVS）,它使用一个虚拟的栈并配合一个位置向量来“缓存”流中遇到的所有关键字。在XVS的基础上,我们给出了kFilter的系统体系结构,并提出了针对多个查询的算法multi-XVS。最后我们分别对XVS和multi-XVS做在时间上和空间上做实验,并且证明我们的算法和系统是高效和可靠的。

论文目录

• 目录
• 摘要
• Abstract
• 第一章 引言
• 1.1 相关研究背景
• 1.2 本文的研究成果
• 1.3 本文组织
• 第二章 概述
• 2.1 XML概述
• 2.1.1 什么是 XML
• 2.1.2 结构良好的和有效的文档
• 2.1.3 DOM和SAX
• 2.2 XML流处理
• 2.2.1 概况
• 2.2.2 当前研究状况
• 2.2.3 存在的问题
• 2.3 XML文档上关键字查询
• 2.3.1 概况
• 2.3.2 当前研究状况
• 2.4 XML流上关键字查询
• 2.4.1 概况
• 2.4.2 存在的问题
• 2.5 本章小结
• 第三章 SLCA和SAX模型
• 3.1 基本概念
• 3.1.1 文档的树模型
• 3.1.2 SLCA节点
• 3.2 SAX模型
• 3.3 几点说明
• 3.4 本章小结
• 第四章 单查询算法
• 4.1 初始算法
• 4.2 最右包含边界
• 4.3 XVirtualStack算法
• 4.4 算法示例
• 4.5 算法分析
• 4.6 本章小结
• 第五章 系统结构和多查询算法
• 5.1 系统结构
• 5.2 多查询算法multi-XVS
• 5.3 算法示例
• 5.4 本章小结
• 第六章 实验
• 6.1 实验环境
• 6.2 XVS实验结果与分析
• 6.3 multi-XVS实验结果与分析
• 6.3.1 时间性能及分析
• 6.3.2 空间性能及分析
• 6.4 本章小结
• 第七章 全文总结与将来工作
• 参考文献
• 致谢
• 附录 攻读硕士学位期间发表的论文