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

作者：孔令波; 唐世渭; 杨冬青; 王腾蛟; 高军

来源：软件学报, 2007, (04): 919-932.

• XML索引
• Dewey编码
• XML信息检索
• 关键字查询
• SLCA
• ILE XML index
• Dewey code
• XML information retrieval
• keyword search
• SLCA (smallest lowest common ancestor)
• ILE (indexed lookup eager)

最小子树根节点问题(smallest lowest common ancestor,简称SLCA)是实现XML信息检索研究中关键字查询的一个基本问题,其主旨就是求解所有包含给定关键字的紧致子树的根节点.XU等人给出了3种算法—基于索引的搜索算法(indexed lookup eager,简称ILE)、基于堆栈的算法以及基于扫描的算法(scan eager,简称SE),并通过实验证明ILE算法具有最好的表现.与基于B+树索引结构的ILE算法不同,所给出的新算法,称为LISA(layered intersection scan algorithm)方法.该方法基于SLCA节点按“层”分布的规律,采...

• 单位
  北京大学; 视觉与听觉信息处理国家重点实验室