Parallel Top-K Similarity Join Algorithms Using MapReduce
Parallel Top-K Similarity Join Algorithms Using MapReduce
复制标题
DOI：
10.1109/icde.2012.87
复制
发表时间：
2012-04
期刊：
影响因子：
--
通讯作者：
Younghoon Kim;Kyuseok Shim
中科院分区：
文献类型：
--
作者：
Younghoon Kim;Kyuseok Shim
有很多应用需要在给定的数据库中找到前k个最相似的记录对。然而，计算这样的top-k相似性连接在今天是一个具有挑战性的问题，因为期望处理大量数据的应用程序越来越多。对于这样的数据密集型应用程序，使用MapReduce范式在大型商用机器集群上并行执行程序最近受到了很多关注。在本文中，我们研究了top-k相似性连接算法如何从流行的MapReduce框架中获益。我们首先开发分治和分支定界算法。接下来，我们提出了所有对分区和基本对分区方法，以最大限度地减少map和reduce函数之间的数据传输量。最后，我们不仅用合成的数据集，而且用真实的数据集进行实验。我们的性能研究证实了我们的MapReduce算法的有效性和可扩展性。
There is a wide range of applications that require finding the top-k most similar pairs of records in a given database. However, computing such top-k similarity joins is a challenging problem today, as there is an increasing trend of applications that expect to deal with vast amounts of data. For such data-intensive applications, parallel executions of programs on a large cluster of commodity machines using the MapReduce paradigm have recently received a lot of attention. In this paper, we investigate how the top-k similarity join algorithms can get benefits from the popular MapReduce framework. We first develop the divide-and-conquer and branch-and-bound algorithms. We next propose the all pair partitioning and essential pair partitioning methods to minimize the amount of data transfers between map and reduce functions. We finally perform the experiments with not only synthetic but also real-life data sets. Our performance study confirms the effectiveness and scalability of our MapReduce algorithms.