公开(公告)号：CN102799617A

公开(公告)日：2012-11-28

申请号：CN201210202816.3

申请日：2012-06-19

Applicant: 华中科技大学

Inventor： 曹强 ,  黄建忠 ,  谢长生 ,  荣益麟 ,  慎涵 ,  黄国强

IPC: G06F17/30

Abstract: 本发明公开了一种多层Bloom Filter的构建及查询优化方法，构建时，对现有多层Bloom Filter中各层相关Bloom Filter的bit位进行重新放置，将第一层Q个Bloom Filter以及上层每一个Bloom Filter对应的下层Q个Bloom Filter的相同位置bit位放在同一连续地址空间；查询时，一个哈希值对应同层Q个Bloom Filter的bit位存在于同一连续地址空间，通过对少数连续空间的查询即可实现对进行多层Bloom Filter的查询。本发明优化后的多层Bloom Filter在不增加存储空间的基础上，相应bit位查询操作更为简便，大大减少了磁盘访问的次数，有效减少了对多层Bloom Filter的查询时间。

公开(公告)号：CN102968467A

公开(公告)日：2013-03-13

申请号：CN201210447165.4

申请日：2012-11-10

Applicant: 华中科技大学

Inventor： 曹强 ,  谢长生 ,  黄国强 ,  慎涵

IPC: G06F17/30

Abstract: 本发明公开了一种多层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的查询时间。

公开(公告)号：CN102799617B

公开(公告)日：2014-09-24

申请号：CN201210202816.3

申请日：2012-06-19

Applicant: 华中科技大学

Inventor： 曹强 ,  黄建忠 ,  谢长生 ,  荣益麟 ,  慎涵 ,  黄国强

IPC: G06F17/30

Abstract: 本发明公开了一种多层Bloom Filter的构建及查询优化方法，构建时，对现有多层Bloom Filter中各层相关Bloom Filter的bit位进行重新放置，将第一层Q个Bloom Filter以及上层每一个Bloom Filter对应的下层Q个Bloom Filter的相同位置bit位放在同一连续地址空间；查询时，一个哈希值对应同层Q个Bloom Filter的bit位存在于同一连续地址空间，通过对少数连续空间的查询即可实现对进行多层Bloom Filter的查询。本发明优化后的多层Bloom Filter在不增加存储空间的基础上，相应bit位查询操作更为简便，大大减少了磁盘访问的次数，有效减少了对多层Bloom Filter的查询时间。