Spark环境下基于多维布隆过滤器的星型连接算法

doi:10.11772/j.issn.1001-9081.2016.02.0353

计算机应用 ›› 2016, Vol. 36 ›› Issue (2): 353-357.DOI: 10.11772/j.issn.1001-9081.2016.02.0353

• 第三届CCF大数据学术会议(CCF BigData 2015) • 上一篇下一篇

Spark环境下基于多维布隆过滤器的星型连接算法

周国亮¹, 萨初日拉², 朱永利²

1. 国网冀北电力有限公司技能培训中心, 河北保定 071051;
2. 华北电力大学控制与计算机工程学院, 河北保定 071003

收稿日期:2015-09-15 修回日期:2015-09-23 出版日期:2016-02-10 发布日期:2016-02-03
通讯作者: 周国亮(1978-),男,河北保定人,副教授,博士,主要研究方向:智能电网、联机分析处理。
作者简介:萨初日拉(1992-),男(蒙古族),内蒙古通辽人,硕士研究生,主要研究方向:云计算、数据挖掘;朱永利(1963-),男,河北衡水人,教授,博士生导师,博士,CCF高级会员,主要研究方向:人工智能、电力调度自动化系统。
基金资助:
中央高校基本科研业务费专项资金资助项目(13MS103);河北省自然科学基金资助项目(F2014502069)。

Star join algorithm based on multi-dimensional Bloom filter in Spark

ZHOU Guoliang¹, SA Churila², ZHU Yongli²

1. Skill Training Center, State Grid Jibei Electric Power Company, Baoding Hebei 071051, China;
2. School of Control and Computer Engineering, North China Electric Power University, Baoding Hebei 071003, China

Received:2015-09-15 Revised:2015-09-23 Online:2016-02-10 Published:2016-02-03

摘要/Abstract

摘要： 为了适应联机分析处理(OLAP)系统中实时数据高性能分析需求不断提高的需求,提出一种能够适合Spark环境并结合多维Bloom Filter(MDBF)的星型连接算法SMDBFSJ。首先,根据多个维表构建MDBF,利用其占用空间小的特点,广播到所有节点;然后,在本地节点完成事实表过滤操作,事实表不需要在节点间移动数据;最后,过滤后的事实表与维表采用重划分方式进行连接,进而得到最终结果。SMDBFSJ算法避免了事实表数据移动,通过MDBF减小了需要广播的数据量,充分结合了广播连接和重划分连接的优势。实验结果表明了该算法的有效性,在单机和集群环境下,该算法相比重划分连接均获得了3倍左右的性能提升。

关键词: 布隆过滤器, 星型连接, 联机分析处理, Spark

Abstract: To meet the high performance analysis requirements for real-time data in On-Line Analytical Processing (OLAP) system, a new star join algorithm which is suitable for Spark platform was proposed based on Multi-Dimensional Bloom Filter (MDBF), namely SMDBFSJ (Spark Multi-Dimensional Bloom Filter Star Join). First of all, MDBF was built according to the dimension tables and broadcasted to all the nodes based on the feature of small size. Then the fact table was filtered completely on the local node, and there was no data movement between nodes. Finally, the filtered fact table and dimension tables were joined using repartition join model to get the final result. SMDBFSJ algorithm avoides the data moving of fact table, reduces the size of broadcasting data using MDBF, as well as fully combines the advantages of broadcast join and repartition join. The experimental results prove the validity of SMDBFSJ algorithm, in stand-alone and cluster environments. SMDBFSJ algorithm can obtain about three times of performance improvement compared with repartition join in Spark.

Key words: Bloom filter, star join, On-Line Analytical Processing(OLAP), Spark

中图分类号:

TP393.027

周国亮, 萨初日拉, 朱永利. Spark环境下基于多维布隆过滤器的星型连接算法[J]. 计算机应用, 2016, 36(2): 353-357.

ZHOU Guoliang, SA Churila, ZHU Yongli. Star join algorithm based on multi-dimensional Bloom filter in Spark[J]. Journal of Computer Applications, 2016, 36(2): 353-357.

参考文献

[1] LI F, OZSU M T, CHEN G, et al. R-store: a scalable distributed system for supporting real-time analytics[C]//ICDE 2014: Proceedings of the IEEE 30th International Conference on Data Engineering. Washington, DC: IEEE Computer Society, 2014: 40-51.
[2] ZAHARIA M, CHOWDHURY M, DAS T, et al. Resilient distributed datasets: a fault-tolerant abstraction for in-memory cluster computing[C]//NSDI 2012: Proceedings of the 9th USENIX Symposium on Networked Systems Design and Implementation. New York: ACM, 2012: 15-28.
[3] GU R, WANG S, WANG F, et al. Cichlid: efficient large scale RDFS/OWL reasoning with Spark[C]//IPDPS 2015: Proceedings of the IEEE 29th International Parallel & Distributed Processing Symposium. Piscataway: IEEE, 2015: 700-709.
[4] QIU H, GU R, YUAN C, et al. YAFIM: a parallel frequent itemset mining algorithm with Spark[C]//IPDPSW 2014: Proceedings of the 2014 IEEE International Parallel & Distributed Processing Symposium Workshops. Piscataway: IEEE, 2014: 1664-1671.
[5] 张磊,方祝和,周敏奇,等.面向内存计算的连接算法[J]. 华东师范大学学报(自然科学版),2014(5):180-191. (ZHANG L, FANG Z H, ZHOU M Q, et al. Join algorithms towards in-memory computing[J]. Journal of East China Normal University (Natural Science), 2014(5): 180-191.)
[6] HACIGÜMÜŞ H, IYER B, MEHROTRA S. Providing database as a service[C]//ICDE 2002: Proceedings of the 2002 IEEE International Conference on Data Engineering. Washington, DC: IEEE Computer Society, 2002: 29-38.
[7] 卞昊穹,陈跃国,杜小勇,等. Spark上的等值连接优化[J].华东师范大学学报(自然科学版), 2014(5): 261-270. (BIAN H Q, CHEN Y G, DU X Y, et al. Equal-join optimization on Spark[J]. Journal of East China Normal University (Natural Science), 2014(5): 261-270.)
[8] HAN H, JUNG H, EOM H, et al. Scatter-Gather-Merge: an efficient star-join query processing algorithm for data-parallel frameworks[J]. Cluster Computing, 2011, 14(2): 183-197.
[9] ZHOU G, ZHU Y, WANG G. Cache conscious star-join in MapReduce environments[C]//Cloud-I '13: Proceedings of the 2nd International Workshop on Cloud Intelligence. New York: ACM, 2013: Article No. 1.
[10] LIN Y, AGRAWAL D, CHEN C, et al. Llama: leveraging columnar storage for scalable join processing in the MapReduce framework[C]//SIGMOD '11: Proceedings of the 2011 ACM Conference on Management of Data. New York: ACM, 2011: 961-972.
[11] LEE T, KIM K, KIM H-J. Join processing using Bloom filter in MapReduce[C]//RACS '12: Proceedings of the 2012 ACM Research in Applied Computation Symposium. New York: ACM, 2012: 100-105.
[12] 刘威,郭渊博,黄鹏.基于多维布隆过滤器的模式匹配引擎[J].计算机应用,2011, 31(1):107-114. (LIU W, GUO Y B, HUANG P. Patten matching engine based on multi-dimensional Bloom filters[J]. Journal of Computer Applications, 2011, 31(1):107-114.)
[13] HACIGÜMÜŞ H, IYER B, MEHROTRA S. Efficient execution of aggregation queries over encrypted relational databases[C]//DASFAA 2004: Proceedings of the 9th International Conference on Database Systems for Advances Applications, LNCS 2973. Berlin: Springer, 2004: 125-136.
[14] AGRAWAL R, K IERNAN J, SR IKANT R, et al. Order preserving encryption for numeric data[C]//SIGMOD 2004: Proceedings of the ACM SIGMOD International Conference on Management of Data. New York: ACM, 2004: 563-574.

[1]	刘专, 韩瑞琛, 张延松, 陈跃国, 张宇. 面向多核CPU和GPU平台的数据库星形连接优化[J]. 计算机应用, 2021, 41(3): 611-617.
[2]	顾军华, 王锋, 戚永军, 孙哲然, 田泽培, 张亚娟. 基于多尺度卷积特征融合的肺结节图像检索方法[J]. 计算机应用, 2020, 40(2): 561-565.
[3]	刘斌, 何进荣, 李远成, 韩宏. 基于分布式神经网络的苹果价格预测方法[J]. 计算机应用, 2020, 40(2): 369-374.
[4]	章夏杰, 朱敬华, 陈杨. Spark下的分布式粗糙集属性约简算法[J]. 计算机应用, 2020, 40(2): 518-523.
[5]	崔艺馨, 陈晓东. Spark框架优化的大规模谱聚类并行算法[J]. 计算机应用, 2020, 40(1): 168-172.
[6]	程文亮, 王志宏, 周虞, 过弋, 赵俊锋. 面向外汇市场监测的分布式计算框架设计[J]. 计算机应用, 2020, 40(1): 173-180.
[7]	刘靖, 肖冠烽. 基于Spark与粒子滤波算法的公交到站时间预测系统[J]. 计算机应用, 2019, 39(2): 429-435.
[8]	刘子豪, 李凌, 叶枫. 基于SparkR的水文传感器数据的异常检测方法[J]. 计算机应用, 2019, 39(2): 436-440.
[9]	赵文芳, 王京丽, 尚敏, 刘亚楠. 基于粒子群优化和支持向量机的花粉浓度预测模型[J]. 计算机应用, 2019, 39(1): 98-104.
[10]	李龙洋, 董一鸿, 施炜杰, 潘剑飞. SQM:基于Spark的大规模单图上的子图匹配算法[J]. 计算机应用, 2019, 39(1): 46-50.
[11]	李勇, 相中启. 基于计数型布隆过滤器的可排序密文检索方法[J]. 计算机应用, 2018, 38(9): 2554-2559.
[12]	张震, 付印金, 胡谷雨. 基于布隆过滤器的新型混合内存架构磨损均衡策略[J]. 计算机应用, 2018, 38(8): 2230-2235.
[13]	张恩, 金刚刚. 基于同态加密和Bloom过滤器的云外包多方隐私集合比较协议[J]. 计算机应用, 2018, 38(8): 2256-2260.
[14]	崔晨, 郑林江, 韩凤萍, 何牧君. 基于内存的HBase二级索引设计[J]. 计算机应用, 2018, 38(6): 1584-1590.
[15]	顾军华, 霍士杰, 武君艳, 尹君, 张素琪. 求解最大团问题的并行多层图划分方法[J]. 计算机应用, 2018, 38(12): 3425-3432.

Spark环境下基于多维布隆过滤器的星型连接算法

Star join algorithm based on multi-dimensional Bloom filter in Spark

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics