序列数据的相似性查询研究

论文摘要

序列数据是一种重要而特殊的数据类型,广泛存在于文本、Web访问序列、交易数据库中的用户购买序列以及生物数据库中的DNA和蛋白质序列等应用中。从直观上看,序列是（值,序）信息对的有序链表,区别于传统的集合数据,其不同元素间具有独特的时间序或空间序关系。序列中元素的值与序关系对分析和挖掘各种序列数据缺一不可。字符序列是一类具有空间序的常见序列数据。各种字符序列数据的分析和挖掘一直是学术界和工业界共同关注的问题。近年来,随着生物信息领域各种生物数据的爆炸式增长,字符序列数据库呈现出横向长度不断增长和纵向数据量不断加大的特点。此外,由于Web技术的迅速发展和Internet用户数量的激增,基于关键字的搜索引擎和邮件系统中的字符拼写检查器,以及数据清洗中的副本检测等应用,对字符序列的高效查询研究也提出了严峻的挑战。序列相似性连接是相似性查询研究的扩展,即找到所有满足一定相似性阈值的序列对,其中序列对中的每条序列分别来自给定的两个序列集。相似性连接在数据清洗、剽窃检测和生物信息等中广泛应用。作为重要的数据分析技术,字符序列的相似性查询和连接研究迄今为止都非常活跃。字符序列相似性查询和连接研究的一个核心问题是序列数据特征的提取和相似性度量的定义及有效计算。由于字符序列具有特征难以抽取及有效表达、相似性度量的计算量较大等特点,使得对其进行有效查询成为研究难点。现有关于字符序列的大多相似性查询算法中,基本只利用基于序列自身特征的多种过滤器来加速算法运行,且在应用多过滤器时完全忽略过滤顺序对算法效率的影响。此外,在查询不断到来时,现有算法基本把先前的查询结果信息丢弃而没有加以利用来加速当前查询,且后处理也基本上是直接的编辑距离计算而没加以优化。而在相似性连接方面的大多数研究中,只针对静态序列集做优化设计,不适合现实应用中高度动态变化的数据环境。因此,针对以上不足,本文对字符序列数据的相似性查询和连接算法进行了系统研究,主要成果概括为以下三方面:（1）.提出优化多重过滤的序列相似性查询算法SSQMF。序列自身特征和度量空间性质是序列“内在”和“外在”的两类重要的特征,从两个不同角度刻画了序列数据自身性质以及不同序列之间的关系。但现有查询算法只基于序列自身特征或空间性质进行过滤,没有把两者很好地结合起来进一步提高算法的过滤能力,且没有分析多过滤器的执行顺序对算法性能的影响。算法SSQMF是有机结合了序列“内在”和“外在”特征的多重过滤器算法,且从理论上提出了一种多过滤器的最优过滤顺序模型,使得SSQMF在整体过滤水平和过滤代价方面得到进一步优化。详细的实验对比表明,SSQMF在查询性能上明显优于单一类型的过滤器算法和基于“内在”特征多过滤器的随机执行顺序算法。（2）.设计了基于参考集索引的增强序列查询算法IRIIRI算法在现有基于参考集索引技术的基础上,充分利用了先前查询结果中含有的丰富过滤信息,且从理论上证明了能加速当前查询所必须保存的先前查询结果数量下界;此外,IRI加进了基于序列自身的特征来使过滤的上下界更紧,从而使得算法过滤能力更强。在过滤完后的后处理阶段,IRI提出了一种只计算部分动态规划表的方法来提高后处理的效率。在真实的DNA序列和蛋白质序列数据上,实验结果表明算法IRI在查询性能上明显优于现有的基于参考集索引方法RI。（3）.设计了一个在动态增量序列集上的有效相似性连接算法SJ-DASS针对现有相似性连接算法在动态增加的序列数据集上不能高效增量式地运行,提出了动态序列集上高效相似性连接算法SJ-DASS.动态增加序列集是反映现实应用的一种数据模型,本文从序列的空间性质和自身特征出发,设计了基于距离的可增量更新索引结构,且提出了两个基于现有过滤器的更紧的距离下界,从而进一步提高了过滤能力。SJ-DASS在动态增加的实验数据集上,不仅运行时间优于现有算法,而且索引空间也大大减少。本文研究了序列数据中与相似性相关的两个问题:查询和连接,并分别提出了有效的解决方案。本文提出的IRI和SSQMF算法对现有技术进行了有效地改进,而提出的SJ-DASS算法则使得静态数据集上的相似性连接有效地扩展到一般的动态应用环境。理论分析证明这些算法高效地解决了相应的问题;大量的对比实验也表明,与现有技术相比本文提出的算法在存储空间、处理速度等方面具有明显的优势。

论文目录

• 目录
• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 应用背景
• 1.2 预备知识
• 1.3 面临的挑战及研究现状
• 1.4 本文的研究成果
• 1.5 本文的组织
• 第二章 序列相似性查询与连接研究综述
• 2.1 序列相似性度量
• 2.1.1 相似性度量的种类
• 2.1.2 序列间距离分布的统计信息
• 2.2 序列相似性查询与连接的关键技术
• 2.2.1 序列相似性查询种类
• 2.2.2 序列相似性查询需解决的核心问题
• 2.2.3 相似性查询的关键技术
• 2.2.4 相似性连接的关键技术
• 2.3 本章小结
• 第三章 优化多重过滤的序列查询算法
• 3.1 相关工作
• 3.2 最优过滤顺序模型
• 3.3 各过滤集基本原理与过滤集大小估计
• 3.3.1 各过滤器的基本过滤原理
• 3.3.2 过滤集大小的在线估计
• MF算法实现'>3.4 SSQ_MF算法实现
• 3.5 实验结果及其分析
• 3.5.1 参数影响
• 3.5.2 整体过滤水平
• 3.5.3 过滤代价
• 3.6 本章小结
• 第四章 基于参考集索引的高效查询算法
• 4.1 相关工作
• 4.2 IRI算法实现过程
• 4.2.1 利用先前查询结果加速当前查询
• 4.2.2 基于序列特征的编辑距离上界和下界
• 4.2.3 后处理中编辑距离的部分计算
• 4.3 实验结果及其分析
• 4.3.1 查询性能
• 4.3.2 参数影响
• 4.4 本章小结
• 第五章 增量序列集上的相似性连接
• 5.1 相关工作
• 5.2 问题描述
• 5.3 基于距离的过滤
• 5.3.1 基于距离的索引结构
• 5.3.2 对BA-Join的进一步过滤
• 5.4 基于序列自身特征的过滤器
• 5.4.1 频率-位置过滤器FP-Filter
• 5.4.2 增强的位置误配过滤器ILM-Filter
• 5.5 实验结果及其分析
• 5.5.1 时间性能比较
• 5.5.2 存储代价比较
• 5.5.3 参数影响
• 5.6 本章小结
• 第六章 总结与未来工作
• 6.1 本文内容总结
• 6.2 未来工作
• 参考文献
• 攻读学位期间作者的工作成果
• 致谢