用 mapreduce 处理 theta-joins

《用 mapreduce 处理 theta-joins》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、用mapreduce处理Theta-joins摘要对于许多数据分析任务来说，连接是基本的（job）,但是mapreduce范式不直接支持它们。在等值连接方面有进展，一般来说，不能充分理解mapreduce里的连接算法的实现。我们研究这个问题：任何吧任意连接条件映射到map和reduce函数，例如：一个只基于key-等值的控制数据库的并行的基本结构。我们提出的连接模型简化了mapreduce里的连接的创建和推理。使用这个模型，我们导出一个惊人的简单的随机算法，叫做1-bucket-theta。这个算法是用来在一个单mapred

2、ucejob实现任意的连接的（theta-joins）.该算法仅仅需要最小的概率（输入基数）。我们有证据表明，对于各种各样的连接问题，它或者接近最优的，或者是最佳的可能的选择。对于1-bucket-theta不是最佳选择的问题，我们显示通过使用附加的输入概率如果来达到更好地性能。所有的算法被制作成‘memory-aware’，它们都不需要对mapreduce环境做任何的修改。实验显示我们的方法的高效性。1.前沿非常大的数据集在许多学科形成一个挑战。英特网公司想分析TB级的应用日志和点击流量数据，科学家必须处理大规模实验和传感

3、器收集的数据集（例如：大型强子碰撞型加速装置，国家虚拟天文台）零售商想找到顾客和销售数据里的模式。当处理这个分析，并行计算对确保合理的响应时间是必要的。Mapreduce已经显示作为最流行的用于并行处理的范式。Mapreduce在数据管理研究方面已经有很大的影响。Mapreduce成功的一个主要的原因是免费开源的实现的可用性，hadoop，和一个活跃的开发者团体。这个团体一直改进mapreduce并添加特性。最近，添加了database-inspiredhigh-level语言（PigLatin）和对SQL查询的支持（Hiv

4、e）。Mapreduce被设计用来处理单个的输入数据集，因此不直接支持连接。但是，最近的研究显示，等值连接已经通过使用mapreduce'skey-equality基于数据库管理实现了。但是在许多应用中，更复杂的连接位置也不要被支持。对于空间数据，band-joins和空间连接很常见。数据集间的关联分析也需要相似的连接。甚至，大家很少关注传统的非等值连接谓词。Map-reduce-merge扩展支持各种连接位置，但是它需要对mapreduce做基本的改变。它如何使用。它不仅添加一个新的合并阶段，而且需要用户写代码。这些代码明

5、确的必须明白这个实现的分布式特性。本人我们提出允许在mapreduce里的任意theta-joins的高效的并行执行。不必要对mapreduce环境进行任何的修改，同时用户也不必要写任何的有专门目的的代码来管理数据流。所有的事情通缩简单的指定合适的（连续的）map和reduce函数来实现。特别的，我们做了如下主要贡献：1.我们提出了一个reducer-centered代价模型和一个连接模型。连接模型简单了mapreduce里可能的theta-join的实现的创建和推理。2.我们提出了一个叫做1-bucket-theta的随机

6、算法，用来计算一个mapreduce任务里的任何的theta-join，包括笛卡尔积。这个算法仅仅需要最小的输入概率（输入集的基数）3.对于一个流行的非等值连接的类，包括非等值和band-joins,我们提出算法，该算法在1-bucket-theta上改进，只要充分的详细的输入是有效的。本人剩下的部分组织如下：我们在第二部分研究了mapreduce和一种普通的等值实现。在第三部分，我们提出了一个定性的mapreduce代价模型和一个连接模型。使用这个连接模型，我们到处1-bucket-theta算法，同时在第五部分，证明它的

7、性能。第六部分显示代表性的实验结果，第七部分讨论了相关工作，第八部分总结了本文。2mapreduce和joins2.1mapreduce综述Mapreduce被提出用来在分布式并行架构上简化大规模数据处理，尤其是商业硬件集群。这个编程模型的主要观点就是隐藏数据分布和负载均衡的细节，让用户注意力集中在数据处理方面。一个mapreduce程序有2个基元组成。Map和reduce。Map函数被应用于单条的输入记录为了计算许多中间结果。对于每一个key，reduce处理带这个key的所有值得列表。任何reduce产生的输出写到分布式

8、文件系统里的一个文件中。Mapreduce构架的综述在图1给出。输入记录可能给分配到分布式文件系统上的多个物理位置上。一旦mapreduce工作被初始化。这些记录被转移到mapper节点上。对于每一个输入记录，执行一个新的map的实体。它把记录解析成一个类型（k1,v1）key/value