TY - CHAP

T1 - An efficient partition based method for exact set similarity joins

AU - Deng, Dong

AU - Li, Guoliang

AU - Wen, He

AU - Feng, Jianhua

PY - 2016

Y1 - 2016

N2 - We study the exact set similarity join problem, which, given two collections of sets, finds out all the similar set pairs from the collections. Existing methods generally utilize the prefix filter based framework. They generate a prefix for each set and prune all the pairs whose prefixes are disjoint. However the pruning power is limited, because if two dissimilar sets share a common element in their prefixes, they cannot be pruned. To address this problem, we propose a partition- based framework. We design a partition scheme to partition the sets into several subsets and guarantee that two sets are similar only if they share a common subset. To improve the pruning power, we propose a mixture of the subsets and their 1-deletion neighborhoods (the subset of a set by eliminating one element). As there are multiple allocation strategies to generate the mixture, we evaluate difierent allocations and design a dynamic-programming algorithm to select the optimal one. However the time complexity of generating the optimal one is O(s3) for a set with size s. To speed up the allocation selection, we develop a greedy algorithm with an approximation ratio of 2. To further reduce the complexity, we design an adaptive grouping mechanism, and the two techniques can reduce the complexity to O(s log s). Experimental results on three real-world datasets show our method achieves high performance and outperforms state- of-the-art methods by 2-5 times.

AB - We study the exact set similarity join problem, which, given two collections of sets, finds out all the similar set pairs from the collections. Existing methods generally utilize the prefix filter based framework. They generate a prefix for each set and prune all the pairs whose prefixes are disjoint. However the pruning power is limited, because if two dissimilar sets share a common element in their prefixes, they cannot be pruned. To address this problem, we propose a partition- based framework. We design a partition scheme to partition the sets into several subsets and guarantee that two sets are similar only if they share a common subset. To improve the pruning power, we propose a mixture of the subsets and their 1-deletion neighborhoods (the subset of a set by eliminating one element). As there are multiple allocation strategies to generate the mixture, we evaluate difierent allocations and design a dynamic-programming algorithm to select the optimal one. However the time complexity of generating the optimal one is O(s3) for a set with size s. To speed up the allocation selection, we develop a greedy algorithm with an approximation ratio of 2. To further reduce the complexity, we design an adaptive grouping mechanism, and the two techniques can reduce the complexity to O(s log s). Experimental results on three real-world datasets show our method achieves high performance and outperforms state- of-the-art methods by 2-5 times.

UR - http://www.scopus.com/inward/record.url?scp=84976517463&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84976517463&partnerID=8YFLogxK

M3 - Chapter

AN - SCOPUS:84976517463

T3 - Proceedings of the VLDB Endowment

SP - 360

EP - 371

BT - Proceedings of the VLDB Endowment

PB - Association for Computing Machinery

T2 - 42nd International Conference on Very Large Data Bases, VLDB 2016

Y2 - 5 September 2016 through 9 September 2016

ER -