Adaptive MapReduce Similarity Joins
Adaptive MapReduce Similarity Joins
复制标题
DOI：
10.1145/3206333.3206340
复制
发表时间：
2018-04
期刊：
影响因子：
--
通讯作者：
Samuel McCauley;Francesco Silvestri
中科院分区：
文献类型：
--
作者：
Samuel McCauley;Francesco Silvestri
相似性连接是一种基本的数据库操作。给定数据集S和R，相似性连接的目标是找到距离不超过r的所有点x ∈ S和y ∈ R。最近的研究已经研究了如何将位置敏感哈希（LSH）用于相似性连接，特别是最近的两项工作在基于LSH的连接性能方面取得了令人兴奋的进展。Hu，Tao和Yi（PODS 17）在大规模并行设置中研究了连接，显示出适应输出大小的强大结果。与此同时，阿勒、Aumüller和Pagh（SODA 17）展示了一种适应数据结构的顺序算法，在最坏的情况下匹配经典边界，但在结构化数据上显着改进。我们表明，这种自适应策略可以适应并行设置，结合这些方法的优点。特别是，我们表明，一个简单的修改胡等人。的算法实现的边界取决于数据集中的点的密度以及输出的总超大值。与其他LSH方法相比，我们的算法不使用额外的参数（特别是，它的执行不依赖于数据集的结构），并且在实践中可能是有效的。
Similarity joins are a fundamental database operation. Given data sets S and R, the goal of a similarity join is to find all points x ∈ S and y ∈ R with distance at most r. Recent research has investigated how locality-sensitive hashing (LSH) can be used for similarity join, and in particular two recent lines of work have made exciting progress on LSH-based join performance. Hu, Tao, and Yi (PODS 17) investigated joins in a massively parallel setting, showing strong results that adapt to the size of the output. Meanwhile, Ahle, Aumüller, and Pagh (SODA 17) showed a sequential algorithm that adapts to the structure of the data, matching classic bounds in the worst case but improving them significantly on more structured data. We show that this adaptive strategy can be adapted to the parallel setting, combining the advantages of these approaches. In particular, we show that a simple modification to Hu et al.'s algorithm achieves bounds that depend on the density of points in the dataset as well as the total outsize of the output. Our algorithm uses no extra parameters over other LSH approaches (in particular, its execution does not depend on the structure of the dataset), and is likely to be efficient in practice.