公开(公告)号：CN102110171A

公开(公告)日：2011-06-29

申请号：CN201110069411.2

申请日：2011-03-22

Applicant: 湖南大学

Inventor： 张大方 ,  黄昆 ,  苏欣 ,  程聂

IPC: G06F17/30

Abstract: 本发明公开了一种基于树形结构的布鲁姆过滤器的查询和更新方法，该方法为：在树形布鲁姆过滤器中存储一定规模或者具有相应特性数据的数据集；读入需要查询的数据集或者需要进行更新操作的数据集；基于树形结构的布鲁姆过滤器元素查询与更新；输出查询和更新结果。本发明可以大大减少误判发生的机率，降低了查询和更新操作所需的时间，增强布鲁姆过滤器的可扩展性，为网络数据存储和数据集成员查询提供保障，它可以应用于数据集中数据成员检测，以及广泛应用于数据库、网络和分布式系统中。

公开(公告)号：CN102110171B

公开(公告)日：2013-05-22

申请号：CN201110069411.2

申请日：2011-03-22

Applicant: 湖南大学

Inventor： 张大方 ,  黄昆 ,  苏欣 ,  程聂

IPC: G06F17/30

Abstract: 本发明公开了一种基于树形结构的布鲁姆过滤器的查询和更新方法，该方法为：在树形布鲁姆过滤器中存储一定规模或者具有相应特性数据的数据集；读入需要查询的数据集或者需要进行更新操作的数据集；基于树形结构的布鲁姆过滤器元素查询与更新；输出查询和更新结果。本发明可以大大减少误判发生的机率，降低了查询和更新操作所需的时间，增强布鲁姆过滤器的可扩展性，为网络数据存储和数据集成员查询提供保障，它可以应用于数据集中数据成员检测，以及广泛应用于数据库、网络和分布式系统中。一种基于树形结构的布鲁姆过滤器的查询与更新方法，其特征在于，该方法为：1)在树形布鲁姆过滤器中存储一定规模或者具有相应特性数据的数据集；2)读入需要查询的数据集或者需要进行更新操作的数据集；3)基于树形结构的布鲁姆过滤器元素查询与更新；4)输出查询和更新结果。根据权利要求1所述基于树形结构的布鲁姆过滤器的查询与更新方法，其特征在于，所述基于树形结构的布鲁姆过滤器元素查询与更新的步骤为：第一步：使用哈希函数对数据集成员进行哈希计算；第二步：对得到的哈希值求模，得到第一层置“1”的比特位在下一层叶子结点应该置“1”的位置；第三步：对第一层置“1”的比特位之前已经置“1”的比特位进行计数，得到叶子结点在下一层叶子结点中的插入位置；第四步：在中间层布鲁姆过滤器中根据得到的索引数据，查询或更新相应位置的叶子结点；第五步：在最后一层查询或更新该层上一层相应比特位之前已经置“1”的比特位的个数，找到最后一层中的相应计数器。