基于Nearest Pair的XML关键词检索算法  

An XML Keyword Retrieval Algorithm Based on Nearest Pair

作　　者：吉聪睿[1] 邓志鸿[1] 唐世渭[1] 

机构地区：[1]北京大学信息科学技术学院智能科学系,北京100871

出　　处：《软件学报》2009年第4期910-917,共8页Journal of Software

基　　金：北京大学-富士通青年基金~~

摘　　要：随着大量数据以XML格式保存,针对XML文档的关键词检索技术已经成为信息检索和数据库等相关领域的研究热点.以树的杜威编码为基础,分析并证明了XML关键词检索中核心概念SLCA(smallest lowest common ancestor)的两个重要性质,并在其基础上提出了Nearest Pair算法.该算法采用二分迭代查找技术寻找最邻近点,将求解中间结果的次数降低了一个量级.实验结果表明,该算法的性能在绝大多数情况下优于现有主流算法.As more and more data are expressed and stored in XML format, the study on XML keyword retrieval becomes the focus of IR （information retrieval） and Database. This paper gives and proves some properties of SLCA （smallest lowest common ancestor）, which is the key concept of XML keyword retrieval. It also introduces a new XML keyword retrieval algorithm, Nearest Pair, on the basis of the properties above. This algorithm uses the iterative hi-search technology to look for nearest pairs, which can decrease the assistant computation by one order of magnitude. The experimental results show that Nearest Pair outperforms the existing mainstream algorithms in most cases

关 键 词：XML 关键词检索 最小公共祖先集合 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]