V-SMART-Join: A Scalable MapReduce Framework for All-Pair Similarity Joins of Multisets and Vectors
V-SMART-Join: A Scalable MapReduce Framework for All-Pair Similarity Joins of Multisets and Vectors
复制标题
DOI：
10.14778/2212351.2212353
复制
发表时间：
2012-04
期刊：
影响因子：
--
通讯作者：
Ahmed A. Metwally;C. Faloutsos
中科院分区：
文献类型：
--
作者：
Ahmed A. Metwally;C. Faloutsos
这项工作提出了V-Smart-Join，这是一个基于MAPREDUCE的可扩展框架，用于发现所有相似实体。 V-Smart-Join框架适用于集合，多组和向量。 V-SMART-JOIN是由观测到的互联网流量的基础分布中观察到的偏斜的动机，并且是一个2阶段算法的家族，第一阶段在其中计算并加入了部分结果，第二阶段为所有人计算了所有相似性候选对。 V-SMART-JOIN算法在实体数量及其基础上非常有效且可扩展。与最小尺寸的真实数据集进行比较时，它们的速度比最先进的算法VCL的状态快30倍。我们还通过将其运行在一个现实尺寸的数据集上，从而确定了提出的算法的可扩展性，VCL从未成功完成。实验是使用IPS和Cookie的真实数据集进行的，其中每个IP被表示为cookie的多组，目标是发现类似的IPS以识别Internet代理。
This work proposes V-SMART-Join, a scalable MapReduce-based framework for discovering all pairs of similar entities. The V-SMART-Join framework is applicable to sets, multisets, and vectors. V-SMART-Join is motivated by the observed skew in the underlying distributions of Internet traffic, and is a family of 2-stage algorithms, where the first stage computes and joins the partial results, and the second stage computes the similarity exactly for all candidate pairs. The V-SMART-Join algorithms are very efficient and scalable in the number of entities, as well as their cardinalities. They were up to 30 times faster than the state of the art algorithm, VCL, when compared on a real dataset of a small size. We also established the scalability of the proposed algorithms by running them on a dataset of a realistic size, on which VCL never succeeded to finish. Experiments were run using real datasets of IPs and cookies, where each IP is represented as a multiset of cookies, and the goal is to discover similar IPs to identify Internet proxies.