Dtrie-allpair: an efficient set T-overlap join algorithm

作者：Jia, Lian-Yin^*; Xi, Jian-Qing; Li, Meng-Juan; You, Jin-Guo; Liu, Yong; Miao, De-Cheng

来源：Journal of South China University of Technology(Natural Science Edition), 2012, 40(6): 109-117.

DOI：10.3969/j.issn.1000-565X.2012.06.018

• Dynamic indices
• Frequency-descending order
• Length-ascending order
• Overlap threshold
• Set similarity

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.

• 出版日期2012-6
• 单位华南理工大学