Dtrie-allpair:高效的集合T-覆盖连接算法

传统的T-覆盖连接算法会因生成的候选集庞大而导致系统性能降低,为此,文中提出了一种基于trie的动态索引结构——DTI结构,并构建了基于该结构的相似度连接算法——Dtrie-allpair算法.通过该算法可以直接得到allpair连接的结果,不产生任何候选集,有效解决了高候选集产生的问题,克服了传统算法因生成并验证候选集而带来的开销.文中还研究了数据库中记录的顺序及记录中元素顺序对Dtrie-allpair算法性能的影响,并在msweb、msnbc两个数据集下对Dtrie-allpair算法与All-pair、PPJoin算法进行对比.结果表明:Dtrie-allpair算法具有明显的优势,覆盖阈值较小时优势更明显;对msweb数据集,阈值为2时,Dtrie-allpair算法的效率相对于All-pair、PPJoin算法提高近两个数量级;通过对数据集进行频率降序和长度升序组合预处理可大幅降低Dtrie-allpair算法访问的trie结点数量,从而显著提升性能.

Dtrie-allpair:an Efficient Set T-Overlap Join Algorithm

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.