Journal of Computer Applications ›› 2011, Vol. 31 ›› Issue (10): 2782-2785.DOI: 10.3724/SP.J.1087.2011.02782

• Artificial intelligence • Previous Articles     Next Articles

cTwigStack: Improved twig pattern matching algorithm

YAO Quan-zhu, GUO Zhen, FANG Mei-jun   

  1. School of Computer Science and Engineering, Xi'an University of Technology, Xi'an Shaanxi 710048, China
  • Received:2011-02-21 Revised:2011-04-22 Online:2011-10-11 Published:2011-10-01
  • Contact: Quan-Zhu YAO

改进的基于小枝模式的匹配算法——cTwigStack

姚全珠[Author]) AND 1[Journal]) AND year[Order])" target="_blank">姚全珠,郭祯,房美君   

  1. 西安理工大学 计算机科学与工程学院,西安 710048
  • 通讯作者: 姚全珠
  • 作者简介:姚全珠(1960-),男,陕西周至人,教授,博士,主要研究方向:数据库技术、软件复用、网络技术;郭祯(1986-),女,陕西周至人,硕士研究生,主要研究方向:数据库;房美君(1986-),女,山西灵石人,硕士研究生,主要研究方向:软件复用。

Abstract: How to quickly locate the interested information in the XML database under a certain twig pattern is a popular research topic. To solve the problem that the TwigStack algorithm for handling the case with parent-child nodes would come out with massive intermediate results, an improved twig pattern query algorithm of cTwigStack was proposed, which was based on caching the non-leaf nodes and delaying the leaf nodes output. The experimental results on Treebank dataset indicate that the proposed algorithm can achieve the most accurate results of the queries that contain the ancestor-descendant relationships below branching nodes. Besides, compared with the present algorithm, it is also highly effective when processing parent-child relationships below branching nodes.

Key words: twig pattern matching, XML database, XML pattern matching, XML document, XPath

摘要: 给定一个小枝模式查询,如何快速地在XML数据集中找到所有感兴趣的信息,已成为当前研究的热点。针对TwigStack算法在处理含有父子节点的情况下会产生大量的中间结果等问题,通过栈来对非叶子节点缓存和对叶子节点延迟输出的思想,提出了一种改进的小枝模式匹配算法——cTwigStack。采用Treebank数据集进行测验,结果表明该算法不仅仅在处理祖孙/后继节点时能使输出结果的准确性达到最优,而且在处理父子节点时,相对目前提出的算法,也是非常高效的。

关键词: 小枝模式匹配, XML数据库, XML模式匹配, XML文档, XPath

CLC Number: