一种高效非归并的XML小枝模式匹配算法

• 作者: 富丽贞 陶世群
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: 小枝模式匹配 归并 主路径 主结点 谓词结点
• 年，卷（期）: 2009,（4）
• 所属期刊栏目: 算法设计与分析
• 页码范围: 795-803
• 页数: 9页
• 分类号: TP301
• 字数: 6876字
• 语种: 中文
• DOI: 10.3724/SP.J.1001.2009.03268

摘要

在XML数据库中,小枝模式查询是XML查询处理的核心操作.近几年,研究人员已提出许多种算法,如Holistic Twig和TJFast算法等.然而它们都是基于归并的,会有很高的计算代价.已提出的Twig2Stack和TwigList算法虽然可以克服这一点,但算法非常复杂.针对这一问题,尤其是考虑了通常查询表达式中只有少数几个结点是最终的输出结点这一特点,提出了TiwgNM算法及其扩展算法TiwgNME算法.算法不需要归并,且只用了少数栈来实现.实验结果表明,这些算法优于以前算法,尤其是对查询中只有祖先.后裔关系的表达式更有效.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	陶世群	山西大学计算机与信息技术学院	58	459	11.0	19.0
2	富丽贞	山西大学计算机与信息技术学院	2	24	2.0	2.0