Optimizing Top-k Similarity Join Algorithm

Similarity join is widely used in data cleaning, data integration and the detection of near duplicate webpages. Existing similarity join algorithms fall into two categories: the threshold-based similarity join and the Top-k similarity join. Top-k similarity join is suitable for applications in which the threshold is unknown in advance. The most efficient Top-k similarity join algorithm is Topk-join, which is proposed by Xiao et al. In order to resolve the performance problems of Topk-join, a novel Top-k similarity join algorithm Opt-join is proposed in this paper. By integrating the token batch processing technique into the existing event-driven framework, Opt-join reduces the cost of processing the prefix events. Also, Opt-join reduces the cost in hash lookup by switching the positions of the hash lookup and filtering operations. The correctness of the new algorithm is proved. Experimental results show that 1.28x-3.09x speed-up is achieved by Opt-join compared with Topk-join. More importantly, with the increase of the