An Efficient Partition Based Method for Exact Set Similarity Joins

Dong Deng, Guoliang Li, He Wen, Jiannan Wang

Abstract

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 partitionbased 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 different allocations and design a dynamic-programming algorithm to select the optimal one. However the time complexity of generating the optimal one is O(s^3) 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 stateof-the-art methods by 2-5 times

Code

Overview

We are happy to release our binary code of setjoin. In this version we only support self-join operation. For further information please send an email to Dong Deng.

Input

Run setjoin on machine with 64bit ubuntu system from command line:

chmod +x setjoin
./setjoin file jac [alpha=1.8] [print=1] > output

Description:

file is the path to the file of the collection of sets where each set is represented by several space separated integers in ascending order. The sets in the file should be sorted in ascending order of size. Sample input file:

2 3 4 5
3 4 5 6
1 2 3 4 5
1 2 3 4 5 6

jac is a float from 0 to 1 which stands for the jaccard threshold.

alpha is a float from 0.5 to 1 used for adaptive grouping.

print boolean controls the output

output stores the result pairs.

Output

It prints 1 lines for each similar pair (string1, string2) and finally outputs the running time, the result number and the candidate number:

3 1
4 3
total time: 0.002s
results: 2 candidates: 2 time: 0.002

Requirement

Have GCC 4.6.4 or higher and a machine running ubuntu 64bit version

Download

Contact

If you have any questions about this study, please feel free to contact Dong Deng.