一种多层Bloom Filter的优化方法及查询方法

摘要

本发明公开了一种多层Bloom Filter的优化方法，包括以下步骤：根据总数据集的大小S确定Bloom Filter的层数N、第一层Bloom Filter个数Q以及底层每个Bloom Filter对应数据集的数据个数M，并设置计数器i=0，判断多层Bloom Filter的构造是否完毕，若未完毕，则接收新数据，判断底层第i个Bloom Filter对应数据集的数据个数是否等于M，若不等于，则使用哈希函数组对新数据进行哈希计算以得到哈希值，将底层Bloom Filter第i个Bloom Filter中与哈希值对应的比特位置1，并对底层Bloom Filter上面的各N-1层进行置位。本发明的方法使比特位查询操作更为简便，大大减少了磁盘访问的次数，有效减少了对多层Bloom Filter的查询时间。

主权项

一种多层Bloom Filter的优化方法，其特征在于，包括以下步骤：（1）根据总数据集的大小S确定Bloom Filter的层数N、第一层BloomFilter个数Q以及底层每个Bloom Filter对应数据集的数据个数M，并设置计数器i=0；其中，多层Bloom Filter各层Bloom Filter个数是以第一层BloomFilter个数Q为首项，公比同为Q的等比数列，且满足QN×M≥S，Q是磁盘扇区容量的整数倍，各层Bloom Filter包含的比特位总数相等；（2）判断多层Bloom Filter的构造是否完毕，若完毕则过程结束，否则进入步骤（3）；（3）接收新数据；（4）判断底层第i个Bloom Filter对应数据集的数据个数是否等于M，若等于，则进入步骤（5），否则进入步骤（6）；（5）设置i=i+1；（6）使用哈希函数组对新数据进行哈希计算以得到哈希值，将底层Bloom Filter第i个Bloom Filter中与哈希值对应的比特位置1，并对底层Bloom Filter上面的各N‑1层进行置位，然后返回步骤（2）。