【作者】 侯进超； 赵合计；

【Author】 Hou Jinchao;Zhao Heji;Shan Dong University;

【机构】 山东大学；

【摘要】 随着互联网的不断发展,XML作为互联网数据交换的标准格式被广泛应用。针对XML文件的过滤问题越来越成为人们研究的重点。而如何在XML数据流上对大量的XPath表达式进行查询处理是XML文件过滤的核心问题。本文围绕XML数据流的查询处理问题展开研究工作,就如何在XML数据流上有效地处理大量路径表达式进行了研究,并针对XPath查询表达式的查询处理技术,提出了一种新的基于有序小枝模式(twig pattern)的XML文件过滤算法(Filtering by Sequencing Twig Patterns,FST)来对XML文件进行过滤,该算法采用改进的普吕弗(Prufer)序列将小枝模式进行分组,借助于特殊的数据结构将XML文档树形结构序列化,并对谓词进行前期处理,将其作为附加信息插入到小枝模式中,从而有效地支持等值谓词和非等值谓词以及逻辑谓词。实验证明,FST算法对于不同特性的数据集均有出色性能。更多还原

【Abstract】 With the uninterrupted development of the Internet,XML is widely used as a standard format of Internet data exchange.The problem of the XML document filtering is becoming more and more important that we are studying.It’ s the core problem of XML document filtering that how to querying and processing the large number of XPath expression in the XML data flow.In this paper,we researched the issue of querying and processing on the XML data flow and discussed how to process the large number of path expression in the XML data flow efficiently and then we proposed a new XML document filter algorithm based on Sequencing Twig Pattern(we call it FST short for Filtering by Sequencing Twig Patterns in this paper) for XML document filtering.The algorithm uses the modified Priifer sequence to group the twig pattern,serializing the tree type structure of XML document with the help of special data structure,preprocessing the predicate and inserting into the twig pattern as overhead information,thus it could support the equality and non-equality operators,and logical operators.The experiment result shows that the FST algorithm has outstanding performance for the data set of different features.更多还原