面向关系数据库的关键字近似搜索技术研究

论文摘要

近年来Web数据大量增长,如何为用户提供有效的搜索技术成为研究的热点。在分布式环境下,通过数据收集,得到的Web数据主要存储在关系数据库中,大量来自不同数据源的Web数据,具有异构模式。在目前的发展阶段,搜索引擎是支持用户查询请求的重要手段。用户根据兴趣,通过搜索引擎接口输入相关的关键字,系统提供快速响应回答用户的请求。很多情况下,用户提交的请求不能与数据库中的数据进行精确匹配,例如：用户对数据了解的程度有限、录入的数据包含错误信息、来自多个数据源的数据存在不一致性等。因此,在关系数据库上有效地支持近似关键字搜索带来了一系列新的挑战,诸如,面向关系数据库的近似查询处理,字符串近似匹配的执行效率和查询结果的排序等问题。本文针对上述问题进行研究,主要工作包括以下几点：（1）为改善对关系元组中字符串数据的近似查询效率,提出一种新颖的索引结构,简称VGRAM （变长GRAM）。与传统的解决近似字符串查询的索引方法相比,VGRAM索引不但节省了近似查询算法的时间,并且将索引的空间缩小了1倍以上。同时,该技术具有很好的可移植性,任何一个基于gram思想的近似字符串查询算法都可以采用该索引技术并提高原有算法的执行效率。其主要思想是：在字符串集合中,选择高质量的变长gram来支持该集合上的查询。重点研究的问题包括：如何从特定集合中选择高质量的gram、如何基于预选的gram将字符串分解成一组变长的gram集合,以及分析两个gram集合间的相似度同它们编辑距离间的关系。基于真实数据集上大量的实验测试结果表明,VGRAM索引技术可以显著地改善最新的三种经典算法的查询性能。（2）提出了基于代价的高质量gram选择技术。当采用基于gram的倒排列表作为索引结构时,索引项gram的选取直接决定索引结构,进而决定近似查询的执行效率。针对gram索引项集和查询性能间的关系,提出一种计算两个字符串公共gram数目的下限的动态规划算法,以提高下限值,从而获得更快的近似匹配时间。系统地分析gram索引结构对近似匹配性能的影响,并提出一个自动构造高质量gram索引项集的算法。在真实数据集上的实验展示了这些技术对查询性能的改善。就目前所知,这是第一个基于代价分析的gram选择方法。（3）针对有限的form查询接口进行查询扩展,提出基于form查询接口的改善近似搜索能力的查询重写技术。很多近似搜索引擎为用户提供form接口,用户通过form接口提交关键字并获得搜索结果。返回给用户的结果大多数是根据填写在查询接口中不同值域内的关键字计算得到的,导致查询结果的查全率（recall）很低。本文提出一种数据挖掘方法,通过对历史查询及其结果进行挖掘分析,得到一组查询重写知识,包括数据项树和推理规则。利用这些重写知识,可以对用户查询进行扩展,以提高基于form的近似搜索能力,特别是查全率。从不同Web网站上随机选取的3,800篇文档组成的测试集上的实验结果表明：所提出的数据挖掘和查询重写方法获得的平均查准率和查全率均高于80%,而假通过率低于2.0%。（4）针对关系数据表之间以及元组间的数据依赖关系,提出一种支持关系数据库的关键字近似搜索的语义评价模型,包括语义相关度计算和语义评分函数。基于提出的语义评分函数,提出两种以数据块为处理单位的Top-k搜索算法,分别为BA（Blocking Algorithm）算法和EBA（Early-stopping Blocking Algorithm）算法。EBA在BA基础上引入了过滤阈值以便尽早终止算法的迭代过程。实验结果显示所提出的语义评分函数保证了搜索结果的高查准率和查全率,BA算法和EBA算法改善了现有方法的查询性能。总之,本文研究了面向关系数据库的关键字近似搜索技术的几个核心问题,并提出了新的解决方案。理论分析和大量基于实际数据集的测试表明所提出的方法的有效性和高效性。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 背景与研究
• 1.2 关键字搜索与关系数据查询
• 1.3 关键字近似搜索技术的重要应用
• 1.4 本文研究内容
• 1.5 本文组织结构
• 第二章 近似搜索技术的相关知识
• 2.1 问题的提出
• 2.2 相关工作
• 2.2.1 索引技术
• 2.2.2 查询扩展
• 2.2.3 评价函数
• 2.3 本章小结
• 第三章 变长GRAM索引技术—VGRAM
• 3.1 引言
• 3.1.1 研究动机
• 3.1.2 相关工作
• 3.2 相关术语
• 3.3 采用变长Gram作为索引项
• 3.3.1 Gram索引项集
• 3.3.2 构造变长Gram
• 3.4 构造Grams索引项
• 3.4.1 收集Gram频率
• 3.4.2 选择Gram索引项的算法—Prune
• 3.5 Grams集合的相似性
• 3.5.1 定长Gram
• 3.5.2 编辑操作对Gram的影响
• 3.5.3 NAG向量
• 3.6 基于VGRAM的近似连接算法
• 3.6.1 基于VGRAM的MergeCount连接算法
• 3.6.2 基于VGRAM的ProbeCluster连接算法
• 3.6.3 基于VGRAM的PartEnum连接算法
• 3.7 实验与分析
• 3.7.1 VGRAM索引结构代价
• 3.7.2 使用VGRAM索引的优点
• max的影响'>3.7.3 q_max的影响
• 3.7.4 频率阂值的影响
• 3.7.5 不同修剪策略的影响
• 3.7.6 对ProbeCount算法的改进
• 3.7.7 对ProbeCluster算法的改进
• 3.7.8 对PartEnum算法的改进
• 3.8 本章讨论与小结
• 第四章 基于代价的高质量GRAM选择算法
• 4.1 引言
• 4.2 背景
• 4.2.1 近似串查询
• 4.2.2 基于定长Gram的索引结构
• 4.2.3 基于变长Gram的索引结构
• 4.3 紧凑公共gram数目的下限
• 4.4 Gram对近似查询的影响
• 4.4.1 对倒排链表的影响
• 4.4.2 对下限的影响
• 4.4.3 对候选集的影响
• 4.5 生成高质量的Gram索引项
• 4.5.1 自动选择高质量gram索引项的算法—GramGen
• 4.5.2 评估Gram的获益
• 4.6 实验与分析
• 4.6.1 使用动态规划缩紧下限的效果
• 4.6.2 Gram索引项的质量
• min'>4.6.3 选择q_min
• 4.6.4 算法GramGen与Prune的比较
• 4.7 本章小结
• 第五章 支持语义关联的查询重写技术
• 5.1 引言
• 5.2 相关工作
• 5.3 Web重写技术
• 5.3.1 数据项树和推理规则的基本概念
• 5.3.2 构建数据项树和推理规则
• 5.4 利用查询用例重写Web查询
• 5.4.1 查询重写规则
• 5.4.2 推理规则的冲突消减
• 5.4.3 复杂度分析
• 5.5 实验结果
• 5.5.1 测试集文档
• 5.5.2 评价指标
• 5.5.3 重写查询的有效性
• 5.5.4 重写规则的有效性
• 5.5.5 查询比较
• 5.6 本章小结
• 第六章 基于语义函数与关键字的搜索技术
• 6.1 引言
• 6.1.1 现有排序函数的缺陷
• 6.1.2 主要贡献
• 6.2 相关工作
• 6.3 问题定义
• 6.4 语义排序函数
• 6.4.1 元组对查询关键字相关度的计算
• 6.4.2 元组间与查询之间的语义相关度
• 6.4.3 语义排序函数
• 6.5 基于语义的搜索算法
• 6.5.1 CNs中扩展非自由元组
• 6.5.2 元组的单调性
• 6.5.3 语义Top-k算法
• 6.6 实验结果
• 6.6.1 语义排序函数的影响
• 6.6.2 k变化对算法的影响
• 6.6.3 不同查询对算法的影响
• 6.7 本章小结
• 第七章 结论
• 7.1 本文的主要贡献与结论
• 7.2 进一步的工作
• 参考文献
• 致谢
• 攻博期间发表的文章
• 科研经历
• 作者简介