论文部分内容阅读
随着互联网、通信等信息技术的飞速发展,全球数据正在以前所未有的速度积累,如何从这些海量数据中挖掘有价值的信息已成为学术界和工业界关注的焦点。数据规模的快速增长伴随着一个重要问题,即规模庞大及来源广泛导致数据质量无法得到有力的保障,数据质量的参差不齐给存储和查询处理带来了严峻的挑战。传统基于精确匹配的查询处理技术已难以应对数据质量下降以及应用需求提高的难题。基于相似度的查询处理是提供近似对象查询和提升数据质量的重要方法,研究者们已经在该领域开展了大量的研究工作,其中基于字符串相似度查询处理的研究具有最广泛的应用需求。 鉴于已有字符串相似度查询领域的研究工作主要是针对静态数据集展开的,本文首先从方法论角度总结了该领域的研究进展,从理论和实验的角度分析和对比了主流方法的优缺点。在充分调研和深入分析的基础上,针对已有面向静态数据集的基于删除邻居查询方法存在的不足提出了改进的方法,然后针对海量数据的不同查询处理场景,展开了面向数据流环境和面向分布式查询环境的字符串相似度查询关键技术研究,从时间和空间效率的角度提高了查询处理的性能。本文的主要贡献和创新性工作如下: 1.提出了一种基于删除邻居Trie的字符串相似度查询处理方法。 基于删除邻居的字符串相似度查询方法,其本质是通过字符删除操作将字符串相似度查询问题规约为删除邻居族间的字符串精确匹配问题,是一种以空间换取时间的查询方法。由于删除邻居具有空间复杂度高的缺点,导致索引空间开销很大,难以在实际中应用。针对已有方法的不足,本文提出了基于删除邻居Trie的字符串相似度查询方法DNT-SQ,以编辑距离为度量,有效地融合了删除邻居特征选择度高及Trie共享前缀的优点,并通过索引划分和合并子树的压缩策略进一步降低索引开销,采用位向量删除表降低了验证阶段的时间开销。实验结果表明,与基于删除邻居的最新方法NGPP和SufDN相比,DNT-SQ在有效降低索引空间开销的同时,提升了50%以上的查询处理性能;与算法TrieJoin相比,当阈值大于2时,DNT-SQ将查询处理性能提升了约80%。 2.提出了一种基于滑动窗口的数据流字符串相似度查询处理方法。 数据流是海量数据一种动态存在形式,已有面向数据流的关键字查询处理技术大都是基于精确匹配的,数据流字符串相似度查询处理具有重要的研究价值。本文提出了基于滑动窗口的字符串相似度查询处理方法AS3,该算法基于过滤-验证的框架,以编辑距离为度量,基于基本窗口的滑动窗口更新机制,应用改进的非对称特征提取策略,提出了预剪裁过滤PPF、流统计过滤CFS以及基于坐标的编辑距离验证算法CV,有效解决了数据流字符串相似度查询处理的问题。实验结果表明,与将已有面向静态数据的方法直接用于数据流相比,AS3在有效支持滑动窗口索引实时更新的同时,降低了索引创建时间和空间开销,将查询处理性能提升了约45%;将AS3用于数据流字符串相似度连接查询处理,该方法比在数据流上直接计算相似度连接的方法更加高效。 3.提出了一种基于MapReduce和关键位置过滤规则的海量字符串相似度查询处理方法。 海量数据上的字符串相似度查询处理需要分布式计算框架的支持,基于MapReduce并行计算引擎研究海量字符串相似度查询处理是一种可行的技术路线。已有基于MapReduce框架的字符串相似度查询方法主要是将字符串相似度查询的单机算法在MapReduce框架下的实现,但现有方法未考虑到Map和Reduce任务间因数据复制引起的I/O开销,大大降低了的查询处理性能。针对这个问题,本文提出了基于MapReduce和关键位置过滤的字符串相似度连接的查询处理方法MRVSJ。该方法基于过滤-验证的框架,以集合相似度作为度量,通过提取分词将字符串文本映射为向量,从而将字符串相似度连接问题转换为向量相似度连接问题;通过向量归一化,提出了基于关键位置划分的过滤算法,然后以该过滤算法为核心,在MapReduce框架中进行了实现。MRVSJ分为两个阶段,过滤阶段通过MapReduce任务实现基于关键位置划分的过滤功能并生成候选集,验证阶段通过MapReduce任务对候选集进行验证。实验结果表明,与已有最新方法V-SMART-JOIN和BJOIN相比,MRVSJ提升了约30%的查询处理性能。