| 摘要: |
| 随着大量数据以XML格式保存,针对XML文档的关键词检索技术已经成为信息检索和数据库等相关领域的研究热点.以树的杜威编码为基础,分析并证明了XML 关键词检索中核心概念SLCA(smallest lowest commonancestor)的两个重要性质,并在其基础上提出了Nearest Pair 算法.该算法采用二分迭代查找技术寻找最邻近点,将求解中间结果的次数降低了一个量级.实验结果表明,该算法的性能在绝大多数情况下优于现有主流算法. |
| 关键词: XML 关键词检索 最小公共祖先集合 |
| DOI： |
| 分类号: |
| 基金项目:Supported by the PKU-FUJISU Yong Scholar Foundation of China (北京大学-富士通青年基金) |
|
| An XML Keyword Retrieval Algorithm Based on Nearest Pair |
|
JI Cong-Rui,DENG Zhi-Hong,TANG Shi-Wei
|
| Abstract: |
| 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 anew XML keyword retrieval algorithm, Nearest Pair, on the basis of the properties above. This algorithm uses the iterative bi-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. |
| Key words: XML keyword retrieval SLCA (smallest lowest common ancestor) |
