-
题名XML信息检索中最小子树根节点问题的分层算法
被引量:23
- 1
-
-
作者
孔令波
唐世渭
杨冬青
王腾蛟
高军
-
机构
北京大学计算机科学技术系
-
出处
《软件学报》
EI
CSCD
北大核心
2007年第4期919-932,共14页
-
基金
SupportedbytheNationalNaturalScienceFoundationofChinaunderGrantNo.60503037(国家自然科学基金)
theNationalHigh-TechResearchandDevelopmentPlanofChinaunderGrantNo.2005AA4Z307(国家高技术研究发展计划(863))
theBeijingNaturalScienceFoundationofChinaunderGrantNo.4062018(北京市自然科学基金)
-
文摘
最小子树根节点问题(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码集合以及排序操作.同时,给出了两种实际的算法:LISAI和LISAII,二者的区别在于是否采用Dewey编码到整数的转换.其中,LISAII更具有满意的性能.
-
关键词
XML索引
DEWEY编码
XML信息检索
关键字查询
SLCA
ile
-
Keywords
XML index
Dewey code
XML information retrieval
keyword search
SLCA (smallest lowest common ancestor)
ile (indexed lookup eager)
-
分类号
TP311
[自动化与计算机技术—计算机软件与理论]
-