寻找XLCA的XML数据流TOP-K关键字查询算法

摘要

XML keyword query is a user- convenient information search technique, which is well suited for users who are not familiar with XML query language and the underlying structure. Existing keyword queries on XML data streams often were based on the result set of SIX A, and in order to solve the incompleteness of the SLCA result set, then a result set based on the definition of XLCA was introduced, as far as possible to the query contains all of the results. In this paper sliding window model was proposed to save the XML data stream, then based on the definition of the result set of XLCA, a TOP-K keyword query algorithm was proposed. The algorithm was proved the correctness and completeness theoretically, and analyzed its time and space complexity.%XML关键字查询是一个用户比较方便的信息搜索方法,非常适用于用户在不熟悉XML查询语言和底层结构的情况下进行信息查询.现有的XML数据流上关键字查询多采用查找SLCA结果集的方式,为了解决基于SLCA结果集定义的不完备性,引入了基于XLCA的结果集定义,使其查询包含尽可能全的结果.文中对于XML数据流提出利用滑动窗口模型保存数据,基于XLCA的结果集定义,提出了一种TOP-K关键字查询算法,并从理论上证明了此算法的正确性和查询的完备性,分析了其时间复杂性和空间复杂性.