基于负载均衡的高效布谷鸟过滤器研究
发布时间：2021-07-08 06:29
在各种各样的大数据应用中,高效的近似集合表示和成员判定是至关重要的。与之前的布隆过滤器及其变体相比,最新的布谷鸟过滤器由于其高效的查询效率和对集合元素删除的支持在近似集合表示上展现出强大的优势。然而布谷鸟过滤器在元素插入过程中会出现严重的性能下降。通过理论分析和实验证实,插入性能的急剧下降是因为布谷鸟过滤器在元素插入过程采用了随机选择策略将元素插入到相应的候选桶中。这种随机选择策略会导致布谷鸟过滤器中不同桶之间的负载不均衡,随着布谷鸟过滤器变得越来越满,这种负载的不均衡会变得越来越明显,导致后面的元素插入过程中出现频繁的重定位,布谷鸟过滤器的插入性能严重下降。为了解决这一问题,提出基于负载均衡的高效布谷鸟过滤器利用排队论中的重要原理,“两种选择的力量（The Power of Two Choices）”来进行元素插入过程中候选桶位置的选择。该设计实现了布谷鸟过滤器桶之间的负载均衡,降低了插入过程中的重定位发生概率。为了证明该设计的有效性,将基于负载均衡的高效布谷鸟过滤器应用于现实的应用中,并使用从现实系统中收集的大规模数据进行实验来测试该设计的性能。实验结果表明,与现有的布谷鸟过滤器相...
【文章来源】：华中科技大学湖北省 211工程院校 985工程院校 教育部直属院校
【文章页数】：58 页
【学位级别】：硕士
【部分图文】：
指纹负载分布（i = 445655） 图 3-2 指纹负载分布（i = 471870）
过滤器中当前负载和满的桶的数目之间的关系，所以通过使用公式（2.12）和公式（2.15）可以得到使用随机选择策略的布谷鸟过滤器当前负载和重定位次数期望之间的关系。同理可以通过使用公式（2.12）和公式（2.17）得到使用“两种选择的力量”策略的布谷鸟过滤器当前负载和重定位次数期望之间的关系。为了更直观的展示基于负载均衡的高效布谷鸟过滤器相对于原始的布谷鸟过滤器的优越性，本章首先进行了数值分析模拟实验，分别计算了当前负载和满桶数目之间的数值解和当前负载和重定位次数期望之间的数值解。在模拟实验中，使用了不同负载因子下布谷鸟过滤器中满桶的数目和重定位次数两个指标来比较原始和布谷鸟过滤器和基于负载均衡的高效布谷鸟过滤器的性能差异。还比较了当负载因子为 0.8 和 0.9 时分别使用两种不同策略的布谷鸟过滤器中的负载分布。设置 m=217和 b=4。为了方便起见，设置布谷鸟过滤器的初始负载 （0 ≤ ≤ ）中 00= 4， 01= 1， 02= 1， 03= 1和 04=图 3-3 满桶的数目 图 3-4 重定位次数
过滤器中当前负载和满的桶的数目之间的关系，所以通过使用公式（2.12）和公式（2.15）可以得到使用随机选择策略的布谷鸟过滤器当前负载和重定位次数期望之间的关系。同理可以通过使用公式（2.12）和公式（2.17）得到使用“两种选择的力量”策略的布谷鸟过滤器当前负载和重定位次数期望之间的关系。为了更直观的展示基于负载均衡的高效布谷鸟过滤器相对于原始的布谷鸟过滤器的优越性，本章首先进行了数值分析模拟实验，分别计算了当前负载和满桶数目之间的数值解和当前负载和重定位次数期望之间的数值解。在模拟实验中，使用了不同负载因子下布谷鸟过滤器中满桶的数目和重定位次数两个指标来比较原始和布谷鸟过滤器和基于负载均衡的高效布谷鸟过滤器的性能差异。还比较了当负载因子为 0.8 和 0.9 时分别使用两种不同策略的布谷鸟过滤器中的负载分布。设置 m=217和 b=4。为了方便起见，设置布谷鸟过滤器的初始负载 （0 ≤ ≤ ）中 00= 4， 01= 1， 02= 1， 03= 1和 04=图 3-3 满桶的数目 图 3-4 重定位次数
【参考文献】：
期刊论文
[1]一种采用签名与哈希技术的云存储去重方案[J]. 张桂鹏,匡振曦,陈平华. 计算机工程与应用. 2020(01)
[2]基于排队论综合指标评估的动态负载均衡算法[J]. 王文博,叶庆卫,周宇,陆志华. 电信科学. 2018(07)
[3]基于布隆过滤器所有权证明的高效安全可去重云存储方案[J]. 刘竹松,杨张杰. 计算机应用. 2017(03)
[4]一种基于社交关系的移动缓存替换算法[J]. 邢起源,王菁,闫阿宾,韩燕波. 计算机科学. 2016(06)
[5]海量图片文件存储去重技术研究[J]. 孙有军,张大兴. 计算机应用与软件. 2014(04)
[6]骚扰电话监控系统的研究与设计[J]. 殷春祥,朱晓民,彭刚. 计算机系统应用. 2010(07)
[7]SmartCache:基于兴趣的协作式Web缓存[J]. 陈海涛,卢宇彤,黄遵国. 计算机科学. 2008(12)
本文编号：3271047
【文章来源】：华中科技大学湖北省 211工程院校 985工程院校 教育部直属院校
【文章页数】：58 页
【学位级别】：硕士
【部分图文】：
指纹负载分布（i = 445655） 图 3-2 指纹负载分布（i = 471870）
过滤器中当前负载和满的桶的数目之间的关系，所以通过使用公式（2.12）和公式（2.15）可以得到使用随机选择策略的布谷鸟过滤器当前负载和重定位次数期望之间的关系。同理可以通过使用公式（2.12）和公式（2.17）得到使用“两种选择的力量”策略的布谷鸟过滤器当前负载和重定位次数期望之间的关系。为了更直观的展示基于负载均衡的高效布谷鸟过滤器相对于原始的布谷鸟过滤器的优越性，本章首先进行了数值分析模拟实验，分别计算了当前负载和满桶数目之间的数值解和当前负载和重定位次数期望之间的数值解。在模拟实验中，使用了不同负载因子下布谷鸟过滤器中满桶的数目和重定位次数两个指标来比较原始和布谷鸟过滤器和基于负载均衡的高效布谷鸟过滤器的性能差异。还比较了当负载因子为 0.8 和 0.9 时分别使用两种不同策略的布谷鸟过滤器中的负载分布。设置 m=217和 b=4。为了方便起见，设置布谷鸟过滤器的初始负载 （0 ≤ ≤ ）中 00= 4， 01= 1， 02= 1， 03= 1和 04=图 3-3 满桶的数目 图 3-4 重定位次数
过滤器中当前负载和满的桶的数目之间的关系，所以通过使用公式（2.12）和公式（2.15）可以得到使用随机选择策略的布谷鸟过滤器当前负载和重定位次数期望之间的关系。同理可以通过使用公式（2.12）和公式（2.17）得到使用“两种选择的力量”策略的布谷鸟过滤器当前负载和重定位次数期望之间的关系。为了更直观的展示基于负载均衡的高效布谷鸟过滤器相对于原始的布谷鸟过滤器的优越性，本章首先进行了数值分析模拟实验，分别计算了当前负载和满桶数目之间的数值解和当前负载和重定位次数期望之间的数值解。在模拟实验中，使用了不同负载因子下布谷鸟过滤器中满桶的数目和重定位次数两个指标来比较原始和布谷鸟过滤器和基于负载均衡的高效布谷鸟过滤器的性能差异。还比较了当负载因子为 0.8 和 0.9 时分别使用两种不同策略的布谷鸟过滤器中的负载分布。设置 m=217和 b=4。为了方便起见，设置布谷鸟过滤器的初始负载 （0 ≤ ≤ ）中 00= 4， 01= 1， 02= 1， 03= 1和 04=图 3-3 满桶的数目 图 3-4 重定位次数
【参考文献】：
期刊论文
[1]一种采用签名与哈希技术的云存储去重方案[J]. 张桂鹏,匡振曦,陈平华. 计算机工程与应用. 2020(01)
[2]基于排队论综合指标评估的动态负载均衡算法[J]. 王文博,叶庆卫,周宇,陆志华. 电信科学. 2018(07)
[3]基于布隆过滤器所有权证明的高效安全可去重云存储方案[J]. 刘竹松,杨张杰. 计算机应用. 2017(03)
[4]一种基于社交关系的移动缓存替换算法[J]. 邢起源,王菁,闫阿宾,韩燕波. 计算机科学. 2016(06)
[5]海量图片文件存储去重技术研究[J]. 孙有军,张大兴. 计算机应用与软件. 2014(04)
[6]骚扰电话监控系统的研究与设计[J]. 殷春祥,朱晓民,彭刚. 计算机系统应用. 2010(07)
[7]SmartCache:基于兴趣的协作式Web缓存[J]. 陈海涛,卢宇彤,黄遵国. 计算机科学. 2008(12)
本文编号：3271047
本文链接：https://www.wllwen.com/kejilunwen/ruanjiangongchenglunwen/3271047.html
