关键词: XML模式匹配, 流数据处理, 路径栈算法, 多线程

Abstract: With the arrival of the big-data era, XML files with large scale, huge information and complicated structure have emerged constantly. But the previous XML query matching algorithms can’t effectively solve the matching problem because they need lots of storage space and preliminary parse work. This paper proposes a new parallel XML stream data pattern matching algorithm named PPS (parallel path stream), which is based on the analysis of the core idea of the existing classic matching algorithm and integrates the knowledge on multi-thread parallel. In the process of sequentially parsing XML file as stream pattern, subtree, whose root is the root element of the query pattern, is stored as ordered list and is added into the task list after an effective filtration. Then the matching result can be gotten through parallel operating on the ordered list. The experimental results demonstrate that the PPS can significantly reduce the storage space, the filtration process and the parallel operation can effectively reduce the matching time, beyond that, the PPS has certain advantage in the query path length.

Key words: XML pattern matching, stream data processing, PathStack algorithm, multi-thread