基于双哈希模糊布隆滤波器云存储数据融合方法与流程

1.本发明涉及数据融合领域，具体为一种基于双哈希模糊布隆滤波器云存储数据融合方法。


背景技术：

2.当前已有许多针对iiot(工业物联网)数据的处理方法，例如:基于bloom滤波器的密钥值存储方法；动态bloom(布隆)滤波器数组云存储系统成员身份的有效表示法；可调节bloom过滤器批量数据的插入法和基于sdn的大数据管理方法。这些方法中普遍存在的缺点是查询复杂度随着输入数据量增加而增加，严重影响存储器的空间利用率。


技术实现要素：

3.针对上述存在的技术不足，本发明的目的是提供一种基于双哈希模糊布隆滤波器云存储数据融合方法，其在确保失效数据鲁棒性条件下，使用了双哈希技术将两个布隆滤波器压缩成一个滤波器，两个哈希函数生成k个哈希函数，大大减少了哈希运算的时间，更为有效利用存储容量，提高跨多个区域大数据存储效率。
4.为解决上述技术问题，本发明采用如下技术方案：
5.基于双哈希模糊布隆滤波器云存储数据融合方法，其特征在于，具体步骤如下：
6.1)设置布隆滤波器：布隆滤波器由一个“m”位数组组成，初始设置全部为0，并由一组k个散列函数组成；
7.2)定义问题描述的数学模型：给定具有n个元素的数据流(ds)，即ds＝{x1,x2,
…
,xn}，数学模型为：
8.3)模糊交叉操作：合并a
x
∈bfi[]和by∈bfj[]的元素，其中x＝y；这两个元素在两部分中具有相同的索引，彼此重叠并在上半部分存储为单个模糊值；在此过程中，索引位用于数据压缩；融合的两个布隆滤波器，bfi[]和bfj[]，被称为第一交叉或第一压缩形式；它由符号cr
i,j
表示，并且需要块位和指纹位来表示使用模糊符号存储在其中的元素；
[0009]
模糊交叉操作表示为如下模型：
[0010]
[0011]
其中，nfo表示不执行模糊操作；
[0012]
4)模糊交叉布隆滤波器中的数据插入：模糊交叉布隆滤波器利用bf[]表示，其由m个元素组成，其中一个指纹位与用于压缩操作的每个块位相关联，来自集合s的输入数据使用双哈希方法添加到布隆滤波器中，显著减少计算时间，在所提布隆滤波器变量中，使用双哈希函数来生成k个哈希函数(即)，哈希函数的数学公式如下：
[0013]gi
(x)＝{h1(x)+i
×
h2(x)}mod m
p
[0014]
其中，m
p
是相对于bf(m)大小的最大限制范围(1:m)和最接近素数之间的散列函数的值，m
p
的选择采取生成最佳散列值方式进行选取，插入首先将m大小的数组划分为两个相同大小的布隆滤波器：
[0015][0016]
元素被添加到第i个布隆滤波器中，当bfi[]的填充容量超过阈值填充比(f
thres
)时，插入从bf
i+1
[]开始，在插入的第一级，根据以下散列值，只有块位被设置为1：
[0017][0018]
一旦达到bf
i+1
[]滤波器的阈值，模糊交叉操作被应用在两个滤波器(bfi[]和bf
i+1
[])上，以便在现有的布隆滤波器中为更多的数据存储空间，为使模糊交叉操作有效，m和k应该是2的倍数；
[0019]
5)模糊交叉布隆滤波器中的数据查询：在模糊交叉布隆滤波器中，查询过程始终从活动时隙a开始，如果在第a个时隙中找到元素，则查询过程返回true；否则，扫描将继续，直到a＝1搜索开始，按如下散列查询方式：
[0020][0021]
在以上公式中，哈希索引使用hi表示，在bfi中，如果则yi被认为是bf[a]时隙中集合s的成员，如果第a个位置表示为cr
i,i+1
，然后使用hresult()函数，该函数检查在哈希索引处出现的α,β,γ的数目，并且它们的对应值存储在c
α
,c
β
,c
γ
中，接下来，分别计算bfi[]和bf
i+1
[]的两个隶属函数，如下所示：
[0022][0023]
下面是根据上面定义的hresult()函数得出的结论：
[0024][0025]
查询cr中的一个项目(y∈q)的时间复杂度是o(k)，如果cr
i,i+1
表示时隙bf[i]和bf[i+1]的2n个元素。
[0026]
优选地，步骤2中的数学模型表示：
①
与散列相关的计算成本(cc)最小化；
②
处理动态数据集时的查询复杂性(qc)最优化；
③
用于存储数据的存储器以最大数量的元素可容纳的方式最优化(ea)；
④
假阳性(f
p
)，布隆滤波器的重要性能参数不超过预定限值。
[0027]
本发明的有益效果在于：1、使用模糊交叉操作合并压缩两个布隆滤波器，实现散列数据在两个布隆滤波器的共享容纳，减少海量数据存储需求；2、利用双哈希计算多个哈希函数降低计算成本，对工业物联网网络失效数据的影响很小，数据衰减缓慢，并允许流数据在内存中驻留相当长的时间；3、在不损失精度的情况下高效优化利用存储空间。
具体实施方式
[0028]
下面将结合本发明实施例对本发明的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。
[0029]
基于双哈希模糊布隆滤波器云存储数据融合方法，具体步骤如下：
[0030]
1)设置布隆滤波器：布隆滤波器由一个“m”位数组组成，初始设置全部为0，并由一组k个散列函数组成；
[0031]
2)定义问题描述的数学模型：给定具有n个元素的数据流(ds)，即ds＝{x1,x2,
…
,xn}，主要要求是在存储器和搜索复杂度方面改进现有的布隆滤波器的性能，数学模型为：
[0032]
所述数学模型表示如下问题：
[0033]
①
流数据在很短时间内是可用的，因此必须一次性处理，并在内存中保留足够长时间以便查询；
[0034]
②
与散列相关的计算成本(cc)应最小化；
[0035]
③
处理动态数据集时的查询复杂性(qc)应得到优化；
[0036]
④
用于存储数据的存储器应以最大数量的元素可容纳的方式进行优化(ea)。
[0037]
⑤
假阳性(f
p
)，bloom滤波器的重要性能参数不应超过预定限值；
[0038]
3)模糊交叉操作：合并a
x
∈bfi[]和by∈bfj[]的元素，其中x＝y；这两个元素在两部分中具有相同的索引，彼此重叠并在上半部分存储为单个模糊值；在此过程中，索引位用于数据压缩；融合的两个布隆滤波器，bfi[]和bfj[]，被称为第一交叉或第一压缩形式；它
由符号cr
i,j
表示，并且需要块位和指纹位来表示使用模糊符号存储在其中的元素；
[0039]
模糊交叉操作表示为如下模型：
[0040][0041]
其中，nfo表示不执行模糊操作；
[0042]
当存储在初始m/2空间中，一旦达到可用空间阈值，则空间m/2耗尽，然后应用下一个交叉过程，将存储在m/2空间中的数据移动到m/4空间中，并再次生成一些新的空间，以在相同大小m的布隆滤波器中存储更多传入数据，由于使用模糊交叉，上述存储方法具有唯一签名，它保留了布隆滤波器的两个部分数据，以便在更长的时间内可查询；
[0043]
4)模糊交叉布隆滤波器中的数据插入：模糊交叉布隆滤波器利用bf[]表示，其由m个元素组成，其中一个指纹位与用于压缩操作的每个块位相关联，来自集合s的输入数据使用双哈希方法添加到布隆滤波器中，显著减少计算时间，在所提布隆滤波器变量中，使用双哈希函数来生成k个哈希函数(即)，哈希函数的数学公式如下：
[0044]gi
(x)＝{h1(x)+i
×
h2(x)}mod m
p
[0045]
其中，m
p
是相对于bf(m)大小的最大限制范围(1:m)和最接近素数之间的散列函数的值，m
p
的选择采取生成最佳散列值方式进行选取，插入首先将m大小的数组划分为两个相同大小的布隆滤波器：
[0046][0047]
元素被添加到第i个bloom滤波器中，当的填充容量超过阈值填充比(f
thres
)时，插入从bf
i+1
[]开始，在插入的第一级，根据以下散列值，只有块位被设置为1：
[0048][0049]
一旦达到bf
i+1
[]滤波器的阈值，模糊交叉操作被应用在两个滤波器(bfi[]和bf
i+1
[])上，以便在现有的布隆滤波器中为更多的数据存储空间，为使模糊交叉操作有效，m和k应该是2的倍数；
[0050]
5)模糊交叉布隆滤波器中的数据查询：在模糊交叉布隆滤波器中，查询过程始终从活动时隙a开始，如果在第a个时隙中找到元素，则查询过程返回true；否则，扫描将继续，直到a＝1搜索开始，按如下散列查询方式：
[0051][0052]
在以上公式中，哈希索引使用hi表示，在bfi中，如果则yi被认为是
bf[a]时隙中集合s的成员，如果第a个位置表示为cr
i,i+1
，然后使用hresult()函数，该函数检查在哈希索引处出现的α,β,γ的数目，并且它们的对应值存储在c
α
,c
β
,c
γ
中，接下来，分别计算bfi[]和bf
i+1
[]的两个隶属函数，如下所示：
[0053][0054]
下面是根据上面定义的hresult()函数得出的结论：
[0055][0056]
查询cr中的一个项目(y∈q)的时间复杂度是o(k)，如果cr
i,i+1
表示时隙bf[i]和bf[i+1]的2n个元素。
[0057]
对本发明涉及的云存储数据融合算法进行性能测试，具体内容为：选取pbc0.5.15测试库进行模拟测试，可实现对文件失效情况下的批量审计模型设计，同时选取相关文献三种云存储算法进行对比实验，该测试系统选取的开发语言是c语言。测试系统平台软件选取linux 3.8.0-29，处理器配置为cpu intel(r)e5605@2.55ghz，系统内存大小是32gb，系统硬盘是1tb希捷机械硬盘。
[0058]
设置云存储过程中的数据块大小是|id|＝50b，云存储过程的测试文件大小为1gb，设定模拟测试过程中的文件损坏的最大比例是1％，选取所有数据块中的500组作为模拟对象进行数据审计。实验对比指标首先选取云存储过程中的通信数据开销进行实验对比，为确保测试过程所得结果稳定，每组实验单独运行30次求取实验结果的均值进行对比测试。
[0059]
本发明的设计使用模糊交叉操作合并压缩两个布隆滤波器，实现散列数据在两个布隆滤波器的共享容纳，减少海量数据存储需求；利用双哈希计算多个哈希函数降低计算成本，对工业物联网网络失效数据的影响很小，数据衰减缓慢，并允许流数据在内存中驻留相当长的时间；在不损失精度的情况下高效优化利用存储空间。
[0060]
显然，本领域的技术人员可以对本发明进行各种改动和变型而不脱离本发明的精神和范围。这样，倘若本发明的这些修改和变型属于本发明权利要求及其等同技术的范围之内，则本发明也意图包含这些改动和变型在内。

技术特征：
1.基于双哈希模糊布隆滤波器云存储数据融合方法，其特征在于，具体步骤如下：1)设置布隆滤波器：布隆滤波器由一个“m”位数组组成，初始设置全部为0，并由一组k个散列函数组成；2)定义问题描述的数学模型：给定具有n个元素的数据流(d
s
)，即d
s
＝{x1,x2,
…
,x
n
}，数学模型为：3)模糊交叉操作：合并a
x
∈bf
i
[]和b
y
∈bf
j
[]的元素，其中x＝y；这两个元素在两部分中具有相同的索引，彼此重叠并在上半部分存储为单个模糊值；在此过程中，索引位用于数据压缩；融合的两个布隆滤波器，bf
i
[]和bf
j
[]，被称为第一交叉或第一压缩形式；它由符号cr
i,j
表示，并且需要块位和指纹位来表示使用模糊符号存储在其中的元素；模糊交叉操作表示为如下模型：其中，nfo表示不执行模糊操作；4)模糊交叉布隆滤波器中的数据插入：模糊交叉布隆滤波器利用bf[]表示，其由m个元素组成，其中一个指纹位与用于压缩操作的每个块位相关联，来自集合s的输入数据使用双哈希方法添加到布隆滤波器中，显著减少计算时间，在所提布隆滤波器变量中，使用双哈希函数来生成k个哈希函数(即)，哈希函数的数学公式如下：g
i
(x)＝{h1(x)+i
×
h2(x)}mod m
p
其中，m
p
是相对于bf(m)大小的最大限制范围(1:m)和最接近素数之间的散列函数的值，m
p
的选择采取生成最佳散列值方式进行选取，插入首先将m大小的数组划分为两个相同大小的布隆滤波器：元素被添加到第i个布隆滤波器中，当bf
i
[]的填充容量超过阈值填充比(f
thres
)时，插入从bf
i+1
[]开始，在插入的第一级，根据以下散列值，只有块位被设置为1：一旦达到bf
i+1
[]滤波器的阈值，模糊交叉操作被应用在两个滤波器(bf
i
[]和bf
i+1
[])上，以便在现有的布隆滤波器中为更多的数据存储空间，为使模糊交叉操作有效，m和k
应该是2的倍数；5)模糊交叉布隆滤波器中的数据查询：在模糊交叉布隆滤波器中，查询过程始终从活动时隙a开始，如果在第a个时隙中找到元素，则查询过程返回true；否则，扫描将继续，直到a＝1搜索开始，按如下散列查询方式：在以上公式中，哈希索引使用h
i
表示，在bf
i
中，如果则y
i
被认为是bf[a]时隙中集合s的成员，如果第a个位置表示为cr
i,i+1
，然后使用hresult()函数，该函数检查在哈希索引处出现的α,β,γ的数目，并且它们的对应值存储在c
α
,c
β
,c
γ
中，接下来，分别计算bf
i
[]和bf
i+1
[]的两个隶属函数，如下所示：下面是根据上面定义的hresult()函数得出的结论：查询cr中的一个项目(y∈q)的时间复杂度是o(k)，如果cr
i,i+1
表示时隙bf[i]和bf[i+1]的2n个元素。2.根据权利要求1所述的基于双哈希模糊布隆滤波器云存储数据融合方法，其特征在于，步骤2中的数学模型表示：
①
与散列相关的计算成本(c
c
)最小化；
②
处理动态数据集时的查询复杂性(q
c
)最优化；
③
用于存储数据的存储器以最大数量的元素可容纳的方式最优化(e
a
)；
④
假阳性(f
p
)，布隆滤波器的重要性能参数不超过预定限值。

技术总结
本发明公开了基于双哈希模糊布隆滤波器云存储数据融合方法，具体步骤如下：1)设置布隆滤波器；2)定义问题描述的数学模型；3)模糊交叉操作；4)模糊交叉布隆滤波器中的数据插入；5)模糊交叉布隆滤波器中的数据查询；6)实验分析。本发明的方法使用模糊交叉操作合并压缩两个布隆滤波器，实现散列数据在两个布隆滤波器的共享容纳，减少海量数据存储需求；2、利用双哈希计算多个哈希函数降低计算成本，对工业物联网网络失效数据的影响很小，数据衰减缓慢，并允许流数据在内存中驻留相当长的时间；3、在不损失精度的情况下高效优化利用存储空间。间。


技术研发人员：洪文圳 李冬睿 许国恩 周劲桦 陈玉琴
受保护的技术使用者：洪文圳
技术研发日：2020.11.23
技术公布日：2022/5/25