作者：孔令波; 唐世渭; 杨冬青; 王腾蛟; 高军xml索引dewey编码xml信息检索关键字查询slcaile
摘要：最小子树根节点问题（smallest lowest commonancestor,简称SLCA）是实现XML信息检索研究中关键字查询的一个基本问题，其主旨就是求解所有包含给定关键字的紧致子树的根节点．XU等人给出了3种算法一基于索引的搜索算法（indexed lookup eager,简称ILE）、基于堆栈的算法以及基于扫描的算法（scan eagcr，简称SE），并通过实验证明ILE算法具有最好的表现．与基于B＋树索引结构的ILE算法不同，所给出的新算法，称为LISA（1ayrered intersection scan algorithm）方法．该方法基于SLCA节点按“层”分布的规律，采取了逐层求解SLCA节点的思路，即在获取了包含关键字的节点的Dewey码集合后，通过计算对应于不同关键字、不同层次的Dewey码前缀集合的交集，可以得到对应不同层的SLCA节点与ILE相比，LISA除了只需对应于关键字的节点集合信息以外，不再需要其他复杂的辅助数据结构——全部的信息只是对应不同关键字的Dewey码集合以及排序操作．同时，给出了两种实际的算法：LISAⅠ和LISAⅡ，二者的区别在于是否采用Dewey编码到整数的转换．其中，LISAⅡ更具有满意的性能．
注：因版权方要求，不能公开全文，如需全文，请咨询杂志社
