一种基于MapReduce的最近似k对数据搜索方案

摘要

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 .This paper proposes a top-k closest pairs data search scheme based on MapReduce , firstly, the proposed scheme splits conceptually all pairs of points into partitions , and then the all pair partitioning and the essen-tial pair partitioning methods are proposed , we can correctly find the top-k closest pairs by computing the top-k closest pairs in each partition separately and selecting the top-k closest pairs among the top-k closest pairs from all partitions .We finally perform the experiments with not only synthetic but also real-life data sets .The performance study confirms the effectiveness and scalabili-ty of the proposed MapReduce algorithms .%多种应用场合需要寻找给定数据库中相似度最大的前k对数据。然而由于应用领域需要处理的数据规模呈上升趋势，计算这样的最相似k对数据，难度非常大。提出一种基于MapReduce 的最相似k对数据搜索方案，该方案首先将所有数据对分割成多个组，然后提出所有数据对分组算法和核心数据对分组算法，通过单独计算每个组中的最近似k对数据，从所有组的最近似k对数据中选择相似度最高的k对数据，进而确定最近似k对数据。最后基于合成数据和真实数据进行实验，性能评估结果表明本文MapReduce算法的有效性和可扩展性。