文档介绍：基于XML关键词检索的索引技术
及其相关算法研究与实现
导师:谢昆青邓志鸿
学生:向永清
日期:2013/4/9
XML关键词检索
定义:使用关键词对XML文档集进行检索的一种
信息检索方式
关键问题
如何保存XML文档内的层次结构信息?
◆如何设计高效的XML关键词检索算法?
以平面文本为检索对
半结构数据为检索对
返回整篇文档作为结果
回内部元素作为结果
不考虑文档内部结构
重点考虑文档内部结构
相关应用已经非常成熟
目前还没有成熟的应用
XML关键词检索
检索语义模型
◆SLCA:独立包含所有关
示例: Query(A, B)
键词的节点
◆ELCA:除去子节点外独
立包含所有关键词的节点
◆ XTree:去掉包含所有关
键词的子节点后,还至少
包括一个关键词的节点
包含关系
. 9
SLCACELCACXTree
ELcA:2,8,9
XTree:2,3,8,9
XML关键词检索
≯节点编码方法
◆局部编码
杜威编码示例
◆ Dewey(杜威)编码
0
◆ ORDPATH编码
全局编码
◆前序编码
◆后续编码
Dewey编码
不⊙
◆优点
,0
0,1,I,O
◆直观简单,扩展性好
◆容易判断任意两个节点之间关系
◆容易求得任意两个节点的祖先节点
缺点
◆可能导致索引系统空间效率低下
◆可能导致基于 Dewey编码的XML关键词检索算法效率不高
问题的提出
如何更加有效地保存XML文档内的层次结
构信息?
元素 Dewey编码长度与元素深度成正比的问题
◆基于 Dewey倒排索引的冗余问题
如何设计更加高效而且通用的XML关键词
检索算法?
◆目前主流算法都基于 Dewey倒排索引,算法效
率可能不高
◆目前的算法都只针对某种具体的检索语义模型
足
本文的创新点
本文提出了一种新的XML元素编码方式:LAF编
码。LAF编码弥补了 Dewey编码的不足并能支持
高效XML检索算法
本文提出了一种新的索引结构,即基于LAF编码
的二层索引结构,二层索引不仅能有效解决目前
XML索引中的元余问题,而且能支持更高效的
XML检索算法。
本文第一次利用堆来设计XML关键词检索算法
并采用自底向上的检索策略,HBA算法不仅具有
较高的检索效率,而且能有效支持多种不同的检
索语义模型
目录
≯研究背景
XML关键词检索
问题的提出
本文创新点
本文工作
LAF编码
基于LAF编码的二层索引
◆HBA算法
实验分析
◆数据集
空间效率比较
时间效率比较
参考文献
参加项目
发表论文
LAF编码定义
定义:LAF编码基于树的宽度优先周游(层次遍历),对于
XML树中的一个节点,其LAF编码由3部分组成:节点的
层次遍历序号,其父亲节点的层次遍历序号以及该节点所
在的深度,由于根节点无父节点,其父节点的层次遍历序
号设为-1
LAF编码示例
卜示例
根节点A:0.-
节点E:
节点H:723
节点K:1074
LAF编码性质
性质1:对于任意XML元素,其LAF编码的长度
为3
性质2:LAF编码是稳定的。首先,因为每个元素
的层次遍历序号互不相同,所以对于一个XML元
素的任意两个元素,其LAF编码是不同的。其次
给定一个能构成树的LAF编码集合,其对应的
XML树是唯一的
性质3:对于LAF编码,比较两个LAF编码的大小
只需比较它们层次遍历序号的大小,时间复杂度
为O(1)