大规模字符串连接的并行化研究与应用

摘要

随着互联网的快速发展，信息的传递日益频繁，海量的信息使得个人的接受能力严重超载。如何能够从这些海量信息中准确、快速获取所需内容成为一个急需解决的问题。字符串相似性连接技术是最为有效的解决办法。字符串相似性连接在现实应用中具有深远的意义。它在文本检索、生物信息学、信号处理、入侵检测等领域有着广泛的应用。
　　本文重点研究如何高效地处理大规模字符串相似性连接的问题，并针对该问题提出了两种并行化的解决方案。本文首先深入研究了字符串相似度连接技术，将衡量字符串相似度多种方法，根据处理对象的不同分成了两类，并结合实际的例子展示了算法的计算的过程、结果，以及相似度的计算公式及应用领域。介绍了已有的相似度连接方法，根据算法的处理策略将它们分为两类，接着探讨了这些算法在处理大规模字符串相似性连接问题时的优缺点，进而提出了更加高效的字符串的并行化连接方法。本文的主要贡献有：
　　(1)深入研究了字符串相似性连接过程中所涉及的相关概念及技术，分析发现，现有方法在处理大规模字符串相似性连接问题时效率较低，且容易出现内存不足等问题。
　　(2)提出了一种新的基于内存的并行化连接算法——Para-Join。首先根据每个字符串的区间向量将数据集划分成若干个不相交的子集。为了实现单个子集的连接和两个不同子集间的连接，本文还提出了两种基于划分框架的算法Para-RR和Para-RS。Para-Join算法不仅能保证结果的完整性而且也不会带来冗余计算。它通过多线程编程来实现并行化的字符串连接，提高了字符串相似性连接的效率。
　　(3)针对Para-Join算法无法解决内存不足的问题。本文在Para-Join的基础上提出了一种基于Spark框架的并行化连接算法——Spss-Join，该算法弥补的Para-Join的不足：Spss-Join算法能够自动获取token集而且不需要明确指出线程数量，交由Spark框架自行处理，使得Spss-Join算法更加灵活，能够适应更多的应用和环境；Spss-Join算法解决了内存容量对数据集大小的限制，能有效的处理大规模的数据。
　　(4)结合Para-Join与Spss-Join算法设计并给出了一个基于Spark框架的用于并行化字符串相似性连接的系统原型。
　　理论分析和实验结果表明相比已存在的方法Para-Join是一种更加高效的算法，Spss-Join不仅继承了Para-Join的高效性，同时也使得对于大规模字符串的处理成为了可能。

目录

封面

中文摘要

英文摘要

目录

第1章 绪论

1.1课题背景及意义

1.2国内外研究现状

1.3论文研究内容

1.4论文织结构

第2章 字符串相似性连接技术研究

2.1相关定义及概念

2.2字符串相似度的度量方法

2.3字符串相似性连接方法

2.4本章小结

第3章 基于内存的并行化连接方法

3.1相关符号定义

3.2 Para-Join算法框架

3.3 Para-Join的数据划分及相似度计算

3.4 Para-Join的连接过程

3.5实验结果与分析

3.6本章小结

第4章 基于Spark框架的Spss-Join算法

4.1常见的并行化处理框架

4.2 MapReduce在字符串相似度连接中的应用

4.3基于Spark框架的Spss-Join算法实现

4.4实验结果与分析

4.5本章小结

第5章 系统原型

5.1系统框架

5.2运行结果

5.3本章小结

第6章 总结及展望

6.1论文总结

6.2工作展望

参考文献

致谢

攻读硕士学位期间发表的论文