一种高效的基于图的MLCA求解方法

摘要：

MLCA是判断XML非完全结构查询结果是否有意义的重要方法之一,但目前MLCA求解方法是基于树模型的方法,且对任意一对节点的MLCA求解效率低。采用XML图模型下的基于区间编码的XML存储结构和基于前驱索引集合(SSPI)的引用关系存储结构,结合存储结构提出一种高效的任意节点对的MLCA求解方法。实验表明,与Timber的MLCA算法相比,该方法的运行时间平均降低95％.

关键词： MLCA算法 图模型 区间编码 存储结构 前驱索引集合

作者: 李晓光 乔文 宋宝燕 于戈 任永功

作者单位: 辽宁大学信息学院 沈阳 110036 东北大学信息科学与工程学院 沈阳 110004 辽宁师范大学计算机与信息技术学院 辽宁大连 116029

会议类型: 国内会议

会议名称: 第二十五届中国数据库学术会议(NDBC2008)

会议地点: 桂林

会议语种:中文

页码: 629-634

在线出版日期: 2008-10-24（万方平台首次上网日期，不代表论文的发表时间）