Dynamic Set Similarity Join: An Update Log Based Approach

Chengcheng Yang, Lisi Chen, Hao Wang, Shuo Shang, Rui Mao, Xiangliang Zhang

Research output: Contribution to journalArticlepeer-review

3 Scopus citations


The set similarity join finds all pairs of similar sets from two collections of sets. It has many real world applications, such as personalized recommendation and community mining. In this paper, we study the problem of computing the similarity join in a dynamic context, where the sets are updated dynamically. This, however, is inefficient with the state-of-the-art join methods, because they usually assume that data collections are static and have to compute the join result from scratch whenever a set is updated. To address this issue, we propose ALJoin, an adaptive filtering approach that computes the join result incrementally based on the update logs. We first investigate the effect of set updates on the similarity values, and on this basis we propose to build a neighborhood index for each set. The neighborhood index of a specific set consists of any other sets that can be transformed into its similar sets within a threshold number of update operations. ALJoin then uses this index to effectively identify both similar and dissimilar set pairs based on their update logs. To efficiently build the neighborhood index, we devise several filtering techniques and propose a 'lazy-forward' method to reduce the computational cost. In addition, to improve the efficiency on varying workloads, we propose an analytical cost model, and design an online algorithm with performance guarantees to dynamically consolidate the update logs and adapt the neighborhood indexes. We evaluated our method using four real-world datasets. Experimental results show that our approach outperforms existing methods by up to 3.7×.
Original languageEnglish (US)
Pages (from-to)3727-3741
Number of pages15
Issue number4
StatePublished - Apr 1 2023
Externally publishedYes


Dive into the research topics of 'Dynamic Set Similarity Join: An Update Log Based Approach'. Together they form a unique fingerprint.

Cite this