roundcircle的个人博客分享 http://blog.sciencenet.cn/u/roundcircle

博文

Effective Keyword Search for Valuable LCAs over XML Document

已有 3050 次阅读 2012-11-7 10:59 |系统分类:论文交流|关键词:学者

这篇文章主要解决了SLCA或者XRank等一些方法包含的错误不相关信息以及丢失正确信息的问题。在这篇文章中,作者分别定义它们为false positive(结果集中包含不相关节点) 和 false negative (丢失正确结果节点)问题。SLCA能够避免一些LCA的问题,但是也会遇到其他的 false positive/negative 问题。例如,结果本应该有两个节点,但是一个节点是另一个节点的祖先,因此祖先节点容易被屏蔽,不会出现在结果集合中(PS:我的那篇VMCT解决的都是SLCA的屏蔽性缺陷问题)。
 
基于SLCA的上述问题,作者提出了VLCA(Valuable LCA)的概念,他是基于homogenous(同质)和heterogenous(异质)的概念。VLCA与其他的方法不同之处在于它能够识别具有相同元素类型的节点。定义如下:
(1)Elementary Type:也就是节点在DTD中的标签
(2)Homogenous/Heterogenous:如果LCA到u和v的路径上分别存在两点,并且它们拥有相同的Elementary Type,那么节点u和v是异质的,反之即为同质的。
(3)Valuable LCA:v是n个节点的LCA节点,它也是VLCA节点,当且仅当m个节点是同质的。
然而计算VLCA我们就要判定两个节点是否是同质的,当xml文档类型比较庞大的时候,通常是要花费成本的。作者进一步提出了Meaningful Dewey Code (MDC)来解决的效率问题。
 
MDC是一个简单的计数方法,它同样来源于Dewey Code.通过MDC编码一个xml文件,我们就能够快速的判别祖先节点并且能够识别出两个节点是否是同质的。

为了提高搜索的效率,方法就是将compact VLCA(CVLCA)和基于栈的算法结合起来。CVLCA要比VLCA更加的紧密和有意义。不同于VLCA,CVLCA创建了连接子树用来识别匹配关键字查询的。基于栈的VLCAStack算法要求输入每个关键的MDC排序的反转链表,并且分配一个栈指针。首先,我们先压一个节点到VLCA stack,并且指定一个输入关键字栈的指针。如果VLCAStack包含所有关键字并且是一个CVLCA节点的话,我们将所有的节点弹出栈,并讲当前节点放在结果集合中。如果VLCAStack中的节点不是一个CVLCA的话,那么我们就会继续查找知道我们找出一个CVLCA节点活着栈是空的时候。当VLCAStack和输入列表不是空的时候,我们循环进行这个过程。

为了检测性能,作者将其同Brute-force,XSearch,SLCA和GDMCT的算法进行了elapsed time,precision,recall和f-measures方面的比较。除了运行时间方面,stack-based算法要比其他算法要好。SLCA运行时间要比stack-based算法运行的快,但是它会引起false negative和false positive问题,进而准确率降低。

 



https://m.sciencenet.cn/blog-801343-630061.html


下一篇:Schema-Free XQuery

0

该博文允许注册用户评论 请点击登录 评论 (0 个评论)

数据加载中...

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2024-6-3 06:02

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部