Ed-Sjoin:一种优化的字符串相似连接算法

相似连接(similarity join)在数据清洗、生物信息、模式识别等应用领域中有着广泛应用,其中基于编辑距离的字符串相似连接是一种重要的相似连接.尽管当前有一些基于编辑距离的字符串连接算法提出,然而,当前的算法存在着大量的多余计算,影响了算法的效率.为了高效计算基于编辑距离的字符串连接,提出了一种优化的算法Ed-sjoin,分别从优化筛选算法和基于前缀的重复消减策略两方面对算法进行优化,这些优化策略可以实现更加有效的剪枝,并且避免了部分重复计算,从而加速算法的执行.实验结果表明,提出的方法优于现有方法.

Ed-Sjoin: An Optimal Algorithm for Similarity Joins with Edit Distance Constraints

Similarity join has been widely used in many applications,such as data integration and cleaning,bioinformatics,and pattern recognition.The edit-distance-based similarity join is one of the most important similarity join operators.Recently there are many similarity join algorithms based on edit distance.However,in these algorithms,there is a large amount of redundant calculation,which affects their efficiencies.In the paper,In order to calculate similarity join based on edit distance efficiently,a new algorithm,Ed-Sjoin,is proposed,which exploits two optimal filtering methods and two prefix-based redundant computation reducing methods.Experimental results show that the algorithm presented in this paper is more efficient than existing algorithms.