Join processing using Bloom filter in MapReduce
Join processing using Bloom filter in MapReduce
复制标题
DOI：
10.1145/2401603.2401626
复制
发表时间：
2012-10
期刊：
影响因子：
--
通讯作者：
Taewhi Lee;Kisung Kim;Hyoung-Joo Kim
中科院分区：
文献类型：
--
作者：
Taewhi Lee;Kisung Kim;Hyoung-Joo Kim
MapReduce是一种被广泛用于大规模数据分析的编程模型。连接操作是数据分析的基本操作之一。然而，MapReduce执行联接操作的效率并不高，因为它始终处理数据集中的所有记录，即使在只有一小部分数据集与联接操作相关的情况下也是如此。我们通过应用BloomJoin算法来缓解这个问题，BloomJoin算法是一种经典的分布式连接算法。我们使用MapReduceBloom Filters提高了连接性能。在我们的方法中，Bloom过滤器是以分布式的方式构建的，用于过滤掉冗余的中间记录。为了更好地应用MapReduce中的Bloom过滤器，我们对Hadoop进行了修改，将输入数据集按顺序分配给映射任务，并提出了一种基于估计代价来确定输入数据集的处理顺序的方法。实验结果表明，该体系结构减少了中间结果的数量，提高了连接性能。
MapReduce is a programming model which is extensively used for large-scale data analysis. The join operation is one of the essential operations for the data analysis. However, MapReduce is not very efficient to perform the join operation since it always processes all records in the datasets even in the cases that only small fraction of datasets are relevant for the join operation. We alleviate this problem by applying bloomjoin algorithm, a classic distributed join algorithm. We improve the join performance using Bloom filters in MapReduce. In our approach, the Bloom filters are constructed in distributed fashion and are used to filter out redundant intermediate records. In order to apply the Bloom filters in MapReduce, we modify Hadoop to assign the input datasets to map tasks sequentially, and we propose a method to determine the processing order of input datasets based on the estimated cost. Our experimental results show that the number of intermediate results is decreased and the join performance can be improved in our architecture.