XML信息检索中最小子树根节点问题的分层算法

CORC > 北京大学 > 信息科学技术学院

	XML信息检索中最小子树根节点问题的分层算法; Layered Solution for SLCA Problem in XML Information Retrieval
	孔令波 ; 唐世渭 ; 杨冬青 ; 王腾蛟 ; 高军
刊名	软件学报
	2007
关键词	XML索引 Dewey编码 XML信息检索关键字查询 SLCA ILE
英文摘要	最小子树根节点问题(smallest lowest common ancestor,简称SLCA)是实现XML信息检索研究中关键字查询的一个基本问题,其主旨就是求解所有包含给定关键字的紧致子树的根节点.XU等人给出了3种算法-基于索引的搜索算法(indexed lookup eager,简称ILE)、基于堆栈的算法以及基于扫描的算法(scan eager,简称SE),并通过实验证明ILE算法具有最好的表现.与基于B+树索引结构的ILE算法不同,所给出的新算法,称为LISA(layered intersection scan algorithm)方法.该方法基于SLCA节点按"层"分布的规律,采取了逐层求解SLCA节点的思路,即在获取了包含关键字的节点的Dewey码集合后,通过计算对应于不同关键字、不同层次的Dewey码前缀集合的交集,可以得到对应不同层的SLCA节点.与ILE相比,LISA除了只需对应于关键字的节点集合信息以外,不再需要其他复杂的辅助数据结构--全部的信息只是对应不同关键字的Dewey码集合以及排序操作.同时,给出了两种实际的算法:LISA I和LISA II,二者的区别在于是否采用Dewey编码到整数的转换.其中,LISA II更具有满意的性能.; 国家自然科学基金; 国家高技术研究发展计划(863计划); 北京市自然科学基金; 中文核心期刊要目总览(PKU); 中国科技核心期刊(ISTIC); 中国科学引文数据库(CSCD); 0; 4; 919-932; 18
语种	中文
内容类型	期刊论文
源URL	[http://ir.pku.edu.cn/handle/20.500.11897/224050]
专题	信息科学技术学院
推荐引用方式 GB/T 7714	孔令波,唐世渭,杨冬青,等. XML信息检索中最小子树根节点问题的分层算法, Layered Solution for SLCA Problem in XML Information Retrieval[J]. 软件学报,2007.
APA	孔令波,唐世渭,杨冬青,王腾蛟,&高军.(2007).XML信息检索中最小子树根节点问题的分层算法.软件学报.
MLA	孔令波,et al."XML信息检索中最小子树根节点问题的分层算法".软件学报 (2007).