Efficient Candidate-Free R-S Set Similarity Joins with Filter-and-Verification Trees on MapReduce
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914204903014400 |
|---|---|
| author | Feng, Yuhong Jian, Fangcao Cao, Yixuan Jian, Xiaobin Wang, Jia Feng, Haiyue Miao, Chunyan |
| author_facet | Feng, Yuhong Jian, Fangcao Cao, Yixuan Jian, Xiaobin Wang, Jia Feng, Haiyue Miao, Chunyan |
| contents | Given two different collections of sets R and S, the exact R-S set similarity join (R-S Join) finds all set pairs with similarity no less than a given threshold, which has widespread applications. Existing algorithms accelerate large-scale R-S Joins using a two-stage filter-and-verification framework along with the parallel and distributed MapReduce framework, however, they suffer from excessive candidate set pairs (candidates), leading to significant I/O and verification overhead. This paper proposes novel candidate-free R-S Join (CF-RS-Join) algorithms that integrate filtering and verification into a single stage through the filter-and-verification tree (FVT) and its linear variant (LFVT). First, CF-RS-Join with FVT (CF-RS-Join/FVT) is proposed to leverage an innovative FVT structure that compresses elements and associated sets in memory, enabling single-stage processing that eliminates candidate generation, enables fast lookups, and reduces database scans. Correctness proofs are provided. Second, CF-RS-Join with LFVT (CF-RS-Join/LFVT) is proposed to exploit a more compact Linear FVT, which compresses non-branching paths into single nodes and stores them in linear arrays for optimized traversal. Third, MR-CF-RS-Join/FVT and MR-CF-RS-Join/LFVT are proposed to extend our approaches using MapReduce for parallel processing. Extensive experiments have been conducted on the proposed algorithms against state-of-the-art (SOTA) baselines in terms of execution time, scalability, memory usage, and disk usage. The results show that MR-CF-RS-Join/LFVT outperforms the runner-up by up to 1.37x-15.78x on 7 real-world datasets. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_03893 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Efficient Candidate-Free R-S Set Similarity Joins with Filter-and-Verification Trees on MapReduce Feng, Yuhong Jian, Fangcao Cao, Yixuan Jian, Xiaobin Wang, Jia Feng, Haiyue Miao, Chunyan Distributed, Parallel, and Cluster Computing Databases Given two different collections of sets R and S, the exact R-S set similarity join (R-S Join) finds all set pairs with similarity no less than a given threshold, which has widespread applications. Existing algorithms accelerate large-scale R-S Joins using a two-stage filter-and-verification framework along with the parallel and distributed MapReduce framework, however, they suffer from excessive candidate set pairs (candidates), leading to significant I/O and verification overhead. This paper proposes novel candidate-free R-S Join (CF-RS-Join) algorithms that integrate filtering and verification into a single stage through the filter-and-verification tree (FVT) and its linear variant (LFVT). First, CF-RS-Join with FVT (CF-RS-Join/FVT) is proposed to leverage an innovative FVT structure that compresses elements and associated sets in memory, enabling single-stage processing that eliminates candidate generation, enables fast lookups, and reduces database scans. Correctness proofs are provided. Second, CF-RS-Join with LFVT (CF-RS-Join/LFVT) is proposed to exploit a more compact Linear FVT, which compresses non-branching paths into single nodes and stores them in linear arrays for optimized traversal. Third, MR-CF-RS-Join/FVT and MR-CF-RS-Join/LFVT are proposed to extend our approaches using MapReduce for parallel processing. Extensive experiments have been conducted on the proposed algorithms against state-of-the-art (SOTA) baselines in terms of execution time, scalability, memory usage, and disk usage. The results show that MR-CF-RS-Join/LFVT outperforms the runner-up by up to 1.37x-15.78x on 7 real-world datasets. |
| title | Efficient Candidate-Free R-S Set Similarity Joins with Filter-and-Verification Trees on MapReduce |
| topic | Distributed, Parallel, and Cluster Computing Databases |
| url | https://arxiv.org/abs/2506.03893 |