关键词: 相似性连接;任选前缀;候选;前缀过滤;验证过程

Abstract: Focusing on the similarity join problem， a fuzzy similarity join algorithm was proposed based on dynamic double. The difference from the previous algorithms is that double prefixes are introduced， which improves the filtering efficiency when searching for candidates and building indexes due to the differences of prefixes. On this basis， optimization is realized. First， the candidate set is narrowed by taking the intersection of the candidate sets generated by each prefix. Afterwards， the maximum distinguishing arbitrary-selected prefix is proposed， and this prefix is used for pre-verification to reduce the final candidate pairs that enter the verification process， thereby reducing the join time. Experiments are conducted on three real datasets， and the proposed algorithm is compared with the Silkmoth and MF-Join. The results show that the proposed algorithm can generate a smaller set of candidate set and requires less join time.

Key words: similarity join; arbitrary-selected prefix; candidate; prefix filter; verification process