Effective Early Termination Techniques for Text Similarity Join Operator.pdf

Effective Early Termination Techniques for Text Similarity Join Operator* Selma Ayse ?zalp1, and ?zgür Ulusoy2 1Department of Industrial Engineering, Uludag University, 16059 Gorukle Bursa, Turkey ayseozalp@.tr .tr/~ayseozalp 2Department of Computer Engineering, Bilkent University, 06800 Bilkent Ankara, Turkey oulusoy@.tr Abstract. Text similarity join operator joins two relations if their join attributes are textually similar to each other, and it has a variety of application domains including integration and querying of data from heterogeneous resources; cleansing of data; and mining of data. Although, the text similarity join operator is widely used, its processing is expensive due to the huge number of similarity computations performed. In this paper, we incorporate some short cut evaluation techniques from the Information Retrieval domain, namely Harman, quit, continue, and maximal similarity filter heuristics, into the previously proposed text similarity join algorithms to reduce the amount of similarity computations needed during the join operation. We experimentally evaluate the original and the heuristic based similarity join algorithms using real data obtained from the DBLP Bibliography database, and observe performance improvements with continue and maximal similarity filter heuristics. 1 Introduction The text similarity join operator, as its name implies, joins two relations if their join attributes, which consist of pure text, are highly similar to each other. The similarity between join attributes is determined by well-known techniques such as tf-idf weighting scheme [1] and cosine similarity measure from the Information Retrieval (IR) domain. The text similarity join operator has various application domains. Cohen [2], Gravano et al. [3], and Schallehn et al. [4] use this operator for the integration of data from distributed, heterogeneous databases that lack common formal object identifiers. For instance, in two Web d