标题： 一种高效的无候选项R-S集相似连接算法：基于过滤与验证树和MapReduce 显示英文标题

标题： An Efficient Candidate-Free R-S Set Similarity Join Algorithm with the Filter-and-Verification Tree and MapReduce

摘要： 给定两个不同的集合族，精确的集合相似性R-S连接（R-S Join）找到所有相似度不低于给定阈值的集合对，这在广泛的应用中有重要意义。 尽管现有的算法利用两阶段过滤与验证框架以及并行和分布式MapReduce框架来加速大规模R-S连接，但它们会受到过多候选集对的影响，导致显著的I/O、数据传输和验证开销，并最终降低性能。 本文提出了全新的无候选集的R-S连接（CF-RS-Join）算法，通过过滤与验证树（FVT）及其线性变体（LFVT）将过滤和验证整合到单个阶段。 首先，提出了基于FVT的CF-RS-Join（CF-RS-Join/FVT），利用创新的FVT结构，在内存中压缩元素和相关集合，实现单阶段处理，消除候选集生成、快速查找和减少数据库扫描。 给出了正确性证明。 其次，提出了基于LFVT的CF-RS-Join（CF-RS-Join/LFVT），利用更紧凑的线性FVT，将非分支路径压缩为单个节点并存储在优化的线性数组中。 第三，提出了MR-CF-RS-Join/FVT和MR-CF-RS-Join/LFVT，利用MapReduce扩展我们的方法以实现并行处理。 在7个真实世界的数据集上进行了实验研究，评估所提出的算法在执行时间、可扩展性、内存使用和磁盘使用方面相对于选定现有算法的性能。 实验结果表明，使用MapReduce的算法，即MR-CF-RS-Join/LFVT，表现出最佳性能。 显示英文摘要

摘要： Given two different collections of sets, the exact set similarity R-S Join finds all set pairs with similarity no less than a given threshold, which has widespread applications. While existing algorithms accelerate large-scale R-S Joins using a two-stage filter-and-verification framework along with the parallel and distributed MapReduce framework, they suffer from excessive candidate set pairs, leading to significant I/O, data transfer, and verification overhead, and ultimately degrading the performance. This paper proposes novel candidate-free R-S Join (CF-RS-Join) algorithms that integrate filtering and verification into a single stage through filter-and-verification trees (FVTs) and their linear variants (LFVTs). 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 the candidate set generation, fast lookups, and reduced 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 have been proposed to extend our approaches using MapReduce for parallel processing. Empirical studies on 7 real-world datasets have been conducted to evaluate the performance of the proposed algorithms against selected existing algorithms in terms of execution time, scalability, memory usage, and disk usage. Experimental results demonstrate that our algorithm using MapReduce, i.e., MR-CF-RS-Join/LFVT, achieves the best performance.