摘要
以ELCA的语义为基础,分析ELCA的诸多性质,给出ELCA结果查找算法复杂度高的原因。在其基础上提出BHFA算法,包括2种实现算法BHFAI和BHFAII。该算法计算出分布在各层的LCA,根据ELCA的性质由底向上、向左向右筛选并获取结果。实验结果表明,该算法的查询性能在绝大多数情况下优于现有算法。
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.
出处
《计算机工程》
CAS
CSCD
北大核心
2010年第23期59-62,共4页
Computer Engineering
基金
国家"863"计划基金资助重点项目(2009AA1Z134)
国家自然科学基金资助项目(60803043
60720106001)
关键词
XML检索算法
关键字检索
最小公共祖先
XML retrieval algorithm
keyword retrieval
Lowest Common Ancestors（LCA）
