现实世界中的数据存在着各种各样的错误,例如拼写错误、格式错误、数据不一致等。在分析数据之前,往往需要先对原始数据进行处理和转化,从而得到可用的数据。传统数据处理方式可能丢失很多有效信息甚至引入错误信息,为了得到最佳的分析结果并适应当今大数据时代的需求,论文研究大数据处理中的容错技术。鉴于现实世界中的数据很多都可以用序列或者集合表示,论文利用广泛应用的序列相似函数和集合相似函数来容忍数据的错误。针对数据处理的最典型三个操作:抽取、连接、检索,论文研究了近似抽取、近似连接和近似检索技术来实现错误容忍的数据处理,并设计了高效的索引和算法。论文的主要贡献包括:1.近似抽取:论文提出了一个统一的框架来同时支持序列相似函数和集合相似函数下的近似抽取。基于该统一框架,论文设计了高效的过滤算法来避免不必要的计算并设计了堆算法来共享计算。论文提出了快速有效的剪枝策略来进一步提高抽取性能。实验表明,论文提出的方法比现有最好的方法快1-2个数量级。2.近似连接:论文设计了一个基于划分的框架来支持近似连接,并针对序列相似函数和集合相似函数设计了高效的连接算法。对于序列近似连接,论文把序列平均划分为不相交的片段并保证仅当一个序列的子序列与另一个序列的片段匹配时它们才可能相似。论文提出了有效的子序列选取技术并证明了该技术选取的子序列数量是最少的。论文提出了扩展验证技术来快速验证候选结果。对于集合近似连接,论文根据全集把集合划分为不相交的片段(子集),提出混合使用片段和1-删集(移除片段中1个元素后的子集)来提高过滤能力,设计了动态规划算法来选取最优的混合分配,提出了近似比为2的贪心算法和多长度分组机制来把分配选取时间复杂度从O(s3)降低到O(s log s),其中s是集合大小。论文扩展了这两个算法以运行在MapReduce和Spark上来支持大数据的近似连接。基于划分的算法在EDBT大数据融合竞赛中以绝对优势取得冠军,并且效率比亚军高10倍。3.近似检索:论文提出了一个关键前缀过滤技术来解决基于序列相似性的近似检索问题。相比现有最好的前缀过滤技术,关键前缀过滤技术不但剪枝能力更强而且过滤代价更小。论文设计了动态规划算法来快速选取高质量的关键前缀,能够更好的检测序列中离散的错误。论文还提出了一个对齐过滤技术,能够检测序列中连续的错误。实验表明,关键前缀过滤技术能够过滤掉绝大部分不相似的序列并大幅提高了现有过滤技术的性能。