随着互联网技术的飞速发展和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做在时间上和空间上做实验,并且证明我们的算法和系统是高效和可靠的。