并行的XML数据流模式匹配算法

来源：计算机科学与探索杂志2015年第12期北京时间：

作者：陈冲，蒋夏军，张青平

单位：南京航空航天大学 计算机科学与技术学院，南京 210016

摘要：随着大数据时代的到来，大规模XML文件不断地涌现，其信息庞大，结构复杂，而传统的XML查询匹配技术需要大量的存储空间和预解析工作，不能有效解决XML大文件的匹配要求。针对这种现状，分析了现有经典匹配算法核心思想，并结合多线程并行相关知识，提出了一种新的并行的XML数据流模式匹配算法，称为并行路径流算法（parallel path stream，PPS）。该算法在以流模式顺序解析XML文件的过程中，缓存以查询模式根元素为根节点的子树，以顺序链表存储节点的编码信息，在进行有效过滤后加入任务链表中，采用独特的匹配方法并行操作任务池中的各个顺序链表后得到匹配结果。实验表明，该算法能够明显减少存储空间，其过滤过程和并行操作能够有效减少匹配时间，并在查询路径长度方面具有一定优势。

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