论文部分内容阅读
由于其灵活性和可扩展性,XML成为越来越多互联网上数据的表示标准。在一类应用中,XML数据表现为源源不断到来的数据片断,在这类应用中的XML数据称为XML数据流。XML数据流的应用包括网络信息订阅与发布、电子邮件监测等。在许多应用中,如果用户对XML数据流中数据的模式不了解,则难以写出合适的查询,因而利用关键字对XML数据流进行查询成为一种需要。本文研究了一种面向XML数据流的关键字查询-XML数据流上的TOP-K关键字查询。这类查询在模式未知的情况下,根据用户给出的关键字集合和返回结果数量K,随时给出接收到数据中前K个与关键字集合最相关的XML数据片断。为了有效地处理XML数据流上的TOP-K关键字查询,根据用户需求的不同,本文分别研究了三种XML数据流上的TOP-K关键字查询,并设计了相应算法,其主要研究成果如下:(1)提出了基于打分策略的XML数据流上的TOP-K关键字查询处理方法。具体的,设计了一种打分策略RSR来评价查询结果的相关性;并提出了基于RSR打分策略的XML数据流上的TOP-K关键字查询;提出了一种基于栈的TKS算法,并对算法的时间和空间复杂性进行了分析;设计了一种过滤方法来提高算法的效率和节省存储空间;实验结果表明该算法具有很高的效率和可扩展性。(2)提出了基于skyline的XML数据流上的TOP-K关键字查询处理方法。具体的,考虑到相同的关键字查询可能有不同的查询需求,skyline被应用于XML数据流上的关键字查询,这是XML数据上关键字查询里对查询结果选择的一个新角度;提出了一种新颖的XML数据流上的TOP-K关键字查询:基于松弛skyline的XML数据流上的TOP-K关键字查询,简称为LSK查询;提出了一种有效的基于松弛skyline的XML数据流上的TOP-K关键字查询算法;在LSK查询的基础上提出了多查询下的基于松弛Skyline的XML数据流上的TOP-K关键字查询,简称为MLSK查询;提出了一种有效支持MLSK查询的处理算法MULSK算法;实验结果表明这些算法具有很高的效率和可扩展性。(3)提出了分布式环境下的XML数据流上的TOP-K关键字查询处理。具体的,设计了一种结点上的有效的过滤策略来降低网络吞吐量;证明了使得网络吞吐量最小的网络路由结构设计问题是一个NPC问题;提出了一种设计网络路由结构的启发式算法;通过模拟实验表明算法具有很高的效率和可扩展性,并验证了该算法的有效性。