Error-Tolerant Big Data Processing

Real-world data contains various kinds of errors,e.g.,typos,different formats and inconsistencies.Before analyzing data,one usually needs to process the raw data to get useful data.However,traditional data processing based on exactly match often misses lots of valid information or introduces data with errors.To get high-quality analysis results and fit in the big data era now,this thesis studies the error-tolerant big data processing.As most of the data in real world can be represented as a sequence or set,this thesis utilizes the widely-used sequence-based similarity functions and set-based similar functions to tolerate errors in data processing and studies the approximate entity extraction,similarity join and similarity search problems.The main contributions of this thesis include:1.Approximate Entity Extraction: This thesis proposes a unified framework to support approximate entity extract on both sequence-based and set-based similarity functions simultaneously.Based on this unified framework,this thesis designs efficient filtering algorithms to avoid unnecessary computation and share the other computation.This thesis also proposes efficient and effective pruning techniques to further improve the performance.The experiments show that the method proposed in this thesis can improve the state-of-the-art methods by 1 to 2 orders of magnitude.2.Similarity Join:This thesis designs two partition-based methods respectively for the sequence similarity join and the set similarity join.For the sequence similarity join,this thesis proposes to evenly partition each sequence to multiple segments and guarantees only if a sequence contains a subsequence that matches a segment of another sequence,they can be similar.This thesis proposes effective subsequence selection methods to generate candidates.This thesis proves that the proposed subsequence selection method can select the minimum number of subsequences among all the methods satisfy completeness.This thesis develops an extension-based method and early-termination techniques for efficient candidate verification.For the set similarity join,this thesis proposes to partition all the sets into segments based on the universe and guarantees two sets are similar only if they share a common segment.This thesis proposes to use the mixture of segments and their 1-deletion neighborhoods to improve the pruning power.This thesis evaluates the allocation strategy of the mixture and designs a dynamical programming method to choose the optimal allocation.This thesis develops a greedy algorithm with approximate ratio of 2 and adaptive grouping mechanism to speedup the allocation selection.These two techniques together reduce the time complexity of selecting the allocation for a set with size s from O(s3)to O(s log s).This thesis further extends the two partition-based methods to support the large-scale data processing framework,MapReduce and Spark.The partition-based method won the string similarity join competition held by EDBT and beat the second place by 10 times.3.Similarity Search: This thesis proposes a pivotal prefix filter technique to solve the sequence similarity search problem.This thesis shows that the pivotal prefix filter has stronger pruning power and less filtering cost compared to the state-of-the-art filters.This thesis designs a dynamical programming method to efficiently select high-quality pivotal prefix,which is effective for the non-consecutive errors.This thesis also proposes an alignment filter,which is effective for the consecutive errors.The experiments show that these two techniques can prune most of the dissimilar sequence and improve the performance of the state-of-the-art methods.