Abstract:

As the traditional T-overlap join algorithms generate a huge number of candidates and thus degrade the system performance inevitably,a dynamic trie-based index,DTI,is designed. Based on DTI,a novel similarity join algorithm named Dtrie-allpair is proposed. Dtrie-allpair helps to directly obtain join results without generating candidates and avoids additional overhead. Then,the effects of the order of records in the database and the order of elements in the records on the performance of Dtrie-allpair are investigated. Some experiments are carried out on msweb and msnbc to compare Dtrie-allpair with such algorithms as All-pair and PPJoin. The results show that ( 1) Dtrie-allpair obviously outperforms All-pair and PPJoin,especially at low overlap thresholds; ( 2) at an overlap threshold of 2,the efficiency of Dtrie-allpair is about two orders of magnitude higher than that of All-pair and
PPJoin; ( 3) the preprocess of the dataset with the combination of frequency-descending order and length-ascending order greatly reduces the number of accessed trie nodes and significantly improves the efficiency of Dtrie-allpair.

Key words: set similarity, T-overlap join, overlap threshold, trie-based dynamic index, All-pair algorithm, PPJoin algorithm, frequency-descending order, length-ascending order