基于布隆过滤器的海量数据查询技术的优化与应用

《基于布隆过滤器的海量数据查询技术的优化与应用》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、武汉邮电科学研究院硕士学位论文基于布隆过滤器的海量数据查询技术的优化与应用TheOptimizationandApplicationofBigDataQueryBasedonBloomFilter专业：通信与信息系统研究方向：大数据与云计算导师：卢山研究生：饶文学号：20150030二〇一八年一月武汉邮电科学研究院硕士学位论文摘要随着信息技术、数据库和数据仓库技术等的飞速发展，每时每刻都会有海量的数据产生，对于这些数据的采集、清洗、存储、查询等一系列问题得到了越来越多学者和公司的重视，由此一些数据处理系统，如海量数据查询系统也就产生出来。在

2、这个系统中，查找就是确定一个具有特定值的元素是不是一个特定集合的成员。分布式环境下，随着数据量的增加，为保证系统性能，元素的表示、查找方法常常需要从空间存储、查找效率及准确性等方面来进行考虑。本文基于一个用户行为数据分析的案例，搭建海量用户行为数据查询系统来进行分析与说明。首先对海量数据查询系统进行了需求分析，为获得清晰的数据血缘关系、减少重复开发，从理论上对系统数据仓库进行了分层，对每一层的特点及功能进行了分析，针对每一层的数据流向，设计并实现了原始数据接入模块、原始数据提取模块、付费用户筛选模块等。在整个系统之中，对输入的原始数据进行了

3、采集清洗存储后，在筛选与付费用户筛选模块中，需要在海量数据中判断某账号是否属于付费用户的数据集，布隆过滤器算法提供了一种快速、有效的实现方法。首先简述了直接使用Hive来级联查询的方案，其操作简洁，但解析HiveQL，调用MapReduce程序的过程耗时较长，然后提出使用MongoDB内存数据库存储付费用户的解决方案，其搜索效率很高；如果使用分布式缓存的方法，把付费用户通过合适的数据结构读入内存，这时需要一对一存取，将不同的数据结构HashSet与布隆过滤器算法的时间复杂度、空间复杂度进行了对比，通过分析及实验知，布隆过滤器占用少量的存储开

4、销、查找时间复杂度为常数，解决本类问题极为合适，针对其可能产生的错误数据（“假阳性”）提出消除方案，并进行了实验验证。关键词：查找；海量数据；MapReduce框架；布隆过滤器算法I武汉邮电科学研究院硕士学位论文AbstractWiththedevelopmentofinformationtechnologyandDataWarehousetechonology,thereisahugeamountofdatageneratedallthetime,Moreandmorescholarsandcompanieshavepaidmoreatt

5、entiontothecollection,cleaning,storage,queryofthesedata.Searchingforanelementwithaspecificvalueistoconfirmwhethertheelementisamemberofaparticularset.Withtheincreaseoftheamountofdata,inordertoensurethesystemperformance，elementrepresentationandlookupmethodsoftenneedtoconside

6、rfromtheaspectsofspacecomplexity,timecomplexityandaccuracyrate.Inmanywaystofindelements,bloomfilterbecauseofitslowmemoryconsumption,highsearchefficiency,hasattractedalotofattention.ThisthesismainlystudiestheoptimizationandapplicationofBloomfilteralgorithmofbigdataenvironme

7、nt.ThetheoryandapplicationscenariosofBloomFilterisillustratedbyananalysissampleofcustomerbehaviordata.Firstly,therequirementanalysisofmassivedataqueryframeworkiscarriedout.Inordertoobtaincleardataconsanguinityandreducerepeateddevelopment,thedatawarehouseislayeredtheoretica

8、lly.Thecharacteristicsandfunctionsofeachlayerareanalyzed,andtheoriginaldataaccessmodule,t