主页期刊介绍编委会编辑部服务介绍道德声明在线审稿编委办公编辑办公English
2018-2019年专刊出版计划 微信服务介绍 最新一期:2019年第4期
     
在线出版
各期目录
纸质出版
分辑系列
论文检索
论文排行
综述文章
专刊文章
美文分享
各期封面
E-mail Alerts
RSS
旧版入口
中国科学院软件研究所
  
投稿指南 问题解答 下载区 收费标准 在线投稿
陶世群,富丽贞.一种高效非归并的XML 小枝模式匹配算法.软件学报,2009,20(4):795-803
一种高效非归并的XML 小枝模式匹配算法
An Efficient Algorithm of XML Twig Pattern Matching Without Merging
投稿时间:2007-07-22  修订日期:2008-02-04
DOI:
中文关键词:  小枝模式匹配  归并  主路径  主结点  谓词结点
英文关键词:twig pattern matching  merging  main path  main node  predicate node
基金项目:Supported by the National Natural Science Foundation of China under Grant No.70471003 (国家自然科学基金); the Research Foundation for the Doctoral Program of the Ministry of Education of China under Grant No.20050108004 (高等学校博士学科点专项科研基金)
作者单位
陶世群 山西大学 计算机与信息技术学院,山西 太原 030006 
富丽贞 山西大学 计算机与信息技术学院,山西 太原 030006 
摘要点击次数: 3523
全文下载次数: 4425
中文摘要:
      在XML 数据库中,小枝模式查询是XML 查询处理的核心操作.近几年,研究人员已提出许多种算法,如 Holistic Twig 和TJFast 算法等.然而它们都是基于归并的,会有很高的计算代价.已提出的Twig2Stack 和TwigList 算法虽然可以克服这一点,但算法非常复杂.针对这一问题,尤其是考虑了通常查询表达式中只有少数几个结点是最终的输出结点这一特点,提出了TiwgNM 算法及其扩展算法TiwgNME 算法.算法不需要归并,且只用了少数栈来实现.实验结果表明,这些算法优于以前算法,尤其是对查询中只有祖先-后裔关系的表达式更有效.
英文摘要:
      In an XML database, finding all occurrences of a twig pattern is a core operation for XML query processing. In the past few years, many algorithms, such as Holistic Twig and TJFast, were proposed in theliteratures. However, these algorithms are based on merging, with high computational cost. Recently Twig2Stackalgorithm and TwigList algorithm are proposed to resolve this problem, but they are very complex. Aim at this problem, this paper considers the characteristic that most path expressions have only a few output nodes, and proposes two new algorithms without merging, named TwigNM and TwigNME, which use only a few stacks.Finally, the experimental results show that these algorithms are superior to the previous algorithms, especially for only ancestor-descendant relationship in XPath.
HTML  下载PDF全文  查看/发表评论  下载PDF阅读器
 

京公网安备 11040202500064号

主办单位:中国科学院软件研究所 中国计算机学会
编辑部电话:+86-10-62562563 E-mail: jos@iscas.ac.cn
Copyright 中国科学院软件研究所《软件学报》版权所有 All Rights Reserved
本刊全文数据库版权所有,未经许可,不得转载,本刊保留追究法律责任的权利