You are in:Home/Publications/PreJoin: An Efficient Trie-based String Similarity Join Algorithm

Prof. karam gouda :: Publications:

PreJoin: An Efficient Trie-based String Similarity Join Algorithm
Authors: Karam Gouda and Metwally Rashad
Year: 2012
Keywords: Not Available
Journal: Not Available
Volume: Not Available
Issue: Not Available
Pages: Not Available
Publisher: Not Available
Local/International: International
Paper Link: Not Available
Full paper Karm abdelghany abdelrahman goda_Infos012-Karam_Gouda.pdf
Supplementary materials Not Available

A string similarity join finds all similar pairs between two collections of strings. It is an essential operation in many applications, such as data integration and cleaning, and has attracted significant attention recently. In this paper, we study string similarity joins with edit-distance con- straints. Recently, a Trie-based similarity Join framework is proposed [3]. Existing Trie-based Join algorithms have shown that Trie Indexing is more suitable for Similarity Join on short strings. The main problem with current approaches is that they generate and maintain lots of candidate prefixes called active nodes which need to be further removed. With large edit distance, the number of active nodes becomes quite large. In this paper, we propose a new Trie-based Join algorithm called PreJoin, which improves over current Trie-based Join methods. It efficiently finds all similar string pairs using a new active-node set generation method, and a dynamic preorder traversal of the Trie index. Experiments show that PreJoin is highly efficient for processing short as well as long strings, and outperforms the state-of-the-art Trie-based Join approaches by a factor five.

Google ScholarAcdemia.eduResearch GateLinkedinFacebookTwitterGoogle PlusYoutubeWordpressInstagramMendeleyZoteroEvernoteORCIDScopus