1基于Bloom过滤器的星型连接算法

1．1连接算法在大数据分析应用中，连接是必不可少的一项操作。连接算法通常用于合并2个或多个数据集信息，而连接条件是基于这些数据集共同的一些属性信息。以2个表连接为例，设现有数据表为R（a，b），S（b，c），表R与表S的关联属性为b，对表R和表S做连接操作，根据条件R．b＝S．b，即可找出2个表中满足条件的元组，达到合并2个表的目的。

1．2Bloom过滤器Bloom过滤器是一种空间效率很高的随机数据结构，它主要应用于判断一个元素是否属于某个集合。Bloom过滤器是一个包含m位的bitArray，其初始值均为0，它利用k个相互独立的哈希函数将集合元素映射到｛1，2，…，m｝范围内的k个位置上，其对应位置被置为1。在判断某个元素是否属于集合时，将该元素进行同样的k次哈希运算，若其对应值不全为1，则该元素不是集合中元素；若其对应值全部为1，则认为该元素为集合中元素。但Bloom过滤器存在一定的误判率，如图1所示，X1显然不是集合中元素，而X2可能是结合中元素，也可能恰好为一个误判元素。

1．3基于Bloom过滤器的星型连接算法星型连接是一种典型的多路连接，它是将一个事实表同多个维度表进行连接的操作。基本的星型连接是将事实表与每个维度表分别进行连接操作，再把所有产生的中间结果进行合并得到最终结果。大量中间结果造成巨大的磁盘I／O开销，降低了执行效率。基于Bloom过滤器的星型连接算法是在Map阶段建立n个BF（Ri．Xi）Bloom过滤器以及n个BF（R0．Xi）Bloom过滤器，其中i＝1，2，…，n。在执行星型连接操作时，利用过滤器BF（Ri．Xi）对事实表R0进行过滤操作，利用过滤器BF（R0．Xi）分别对维度表R1，R2，…，Rn进行过滤操作。这样可在Map阶段消除事实表中无连接操作的元组以及大量中间结果。在Reduce阶段，只需执行一次Reduce任务便可完成连接操作。

2连接算法在煤矿安全生产中的应用

在煤矿安全生产过程中，瓦斯浓度、甲烷浓度、一氧化碳浓度、采区温度、粉尘浓度、通风量之间都有着很高的关联性。煤矿安全生产监测系统将采集到的数据存储到数据库中。在对各因素进行相关性分析时，需对各个数据表进行连接操作，根据连接操作结果可分析出影响煤矿安全生产各因素之间的关系。例如，对顶板压力、温度以及甲烷浓度3个数据表进行连接操作，由连接结果可知，当顶板压力不稳定、温度过高、甲烷体积分数大于0．1时，采区处于不安全状态，此时监测系统应发出高危险等级的报警。而通过对粉尘浓度与通风量的数据表连接结果可知，在粉尘浓度急剧增大时需要减少系统的通风量才能保证煤矿生产的安全性。在MapReduce中利用基于Bloom过滤器的星型连接算法对煤矿安全生产数据表进行连接操作，事实表R。

3试验结果分析

试验环境是拥有30个配置完全相同的计算节点的分布式计算平台。在各个节点中均安装Hadoop包作为MapReduce计算环境。试验数据为煤矿安全生产过程中产生的6组真实数据集，表1描述了该6组数据的详细信息。在MapReduce框架中，分别用星型算法（StarJoin）和基于Bloom过滤器的星型连接算法（BFStarJoin）对煤矿安全生产数据集进行测试分析，比较其在连接过程中占用空间的大小和运行时间的长短，分别得出算法的空间性能和执行效率，基于Bloom过滤器的星型连接算法在进行连接操作时占用空间远远低于星型算法，其空间性能大幅度提升。由图5可知，基于Bloom过滤器的星型连接算法在对煤矿安全生产数据集进行分析时有着更好的执行效率。

4结语

利用大数据技术对煤矿安全生产数据进行分析，基于Bloom过滤器的星型连接算法可以将所需分析的煤矿生产过程中各因素所对应的数据表进行有效连接。与传统连接算法相比，该算法在空间性能和执行效率上均有大幅度提升，提高了MapReduce对煤矿生产数据进行连接操作时的处理能力，提升了煤矿安全生产水平。

作者：黄伟力刘影单位：河北工程大学