SSC-Join: An Efficient Syntactic-Semantic Collaboration Based Set Semantic Similarity Join Algorithm

Existing semantic similarity join algorithms assume that all elements in the sets are semantic elements, overlooking the significant impact of syntactic elements. Processing semantic elements requires executing the Hungarian algorithm, leading to high processing costs. To address this challenge, we first introduce signature-based set partitioning, dividing each set into a semantic subset and a syntactic subset while maximizing the number of elements in the syntactic subset to lower semantic processing costs. Second, we design a novel filtering-verification framework. In the filtering phase, we propose efficient signature prefix filtering and collaborative difference filtering methods; signature prefix filtering effectively resolves the issues of conventional prefix filtering failures in set semantic similarity join, while collaborative difference filtering collaboratively exploits the lengths of the syntactic subset and the semantic subset, significantly reducing the number of candidates. Collaborative difference filtering uses only length information for filtering, making it simple and efficient. We theoretically prove that collaborative difference filtering has a higher filtering efficiency than length filtering. In the verification phase, we further propose a semantic-enhanced verification strategy that accelerates the validation speed of the syntactic subset by leveraging the lengths of the unprobed semantic subset. Based on these strategies, we present SSC-Join, which collaboratively utilizes semantic and syntactic subsets. Experimental results on multiple real world datasets demonstrate that SSC-Join can substantially reduce both the number and length of candidates requiring the Hungarian algorithm, offering a performance improvement of up to 679 × over existing algorithms.