Title: Incremental processing for string similarity join

Authors: Cairong Yan; Bin Zhu; Yanglan Gan; Guangwei Xu

Addresses: School of Computer Science and Technology, Donghua University, Shanghai, China ' School of Computer Science and Technology, Donghua University, Shanghai, China ' School of Computer Science and Technology, Donghua University, Shanghai, China ' School of Computer Science and Technology, Donghua University, Shanghai, China

Abstract: String similarity join is an essential operation of data quality management and a key step to find the value of data. An incremental processing framework for string similarity join is proposed in this paper. Compared with the batching processing model, it can avoid the heavy time cost and the space cost brought by the duplicate similarity computation among historical strings and is suitable for processing data streams. We implement two algorithms: Inc-Join and Inp-Join. Inc-Join runs on a stand-alone machine while Inp-Join runs on a cluster with Spark environment. The experimental results show that this incremental processing framework can reduce the amount of string matching without affecting the join accuracy. When the data quantity becomes large, Inp-Join can make full use of the advantage of parallel processing and obtain a better performance than Inc-Join.

Keywords: string similarity join; incremental processing; parallel processing; string matching; Spark; computational science; engineering.

DOI: 10.1504/IJCSE.2019.103780

International Journal of Computational Science and Engineering, 2019 Vol.20 No.2, pp.255 - 268

Received: 30 Jul 2016
Accepted: 22 May 2017

Published online: 29 Nov 2019 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article