摘要： 以ELCA的语义为基础，分析ELCA的诸多性质，给出ELCA结果查找算法复杂度高的原因。在其基础上提出BHFA算法，包括2种实现算法BHFA I和BHFA II。该算法计算出分布在各层的LCA，根据ELCA的性质由底向上、向左向右筛选并获取结果。实验结果表明，该算法的查询性能在绝大多数情况下优于现有算法。

关键词: XML检索算法, 关键字检索, 最小公共祖先

Abstract: This paper gives and analyzes some properties of Exdusive Lowest Common Ancestors(ELCA) based on the semantics of ELCA. It also introduces an XML keyword retrieval algorithm, Bottomup Hierarchical Filtering Algorithm(BHFA), on the basis of the properties above. There are two instances following the BHFA idea, called BHFA I and BHFA II respectively. This algorithm looks for each hierarchical Lowest Common Ancestors(LCA), and gets results through layer by layer selection according to the properties of ELCA. Experimental results show that BHFA outperforms the existing mainstream algorithms in most case.

Key words: XML retrieval algorithm, keyword retrieval, Lowest Common Ancestors(LCA)

中图分类号: 

• TP311