一种基于动态计数型Bloom filter的散列数据表示及查询方法

摘要

本发明公开了一种基于动态计数型Bloom filter(简称DCBF)的散列数据表示及查询方法，包括数据元素的插入、删除和查询。本发明通过建立多个同构计数型Bloom filter和一个ACBF构建了DCBF，该DCBF实现了在无集合元素个数上限的大数据集环境中的高效数据查询，它比原始计数型Bloom filter和动态Bloom filter功能更强大，它在获得高效查询的同时，获得了自适应动态表示大数据集的性能，在大数据集的P2P网络和云计算等环境中查询时可以提高查询效率和节省网络带宽。

主权项

一种基于动态计数型Bloom filter的散列数据表示及查询方法，其特征在于：依次包括以下步骤：a)根据设定的同构计数型Bloom filter可表示的元素上限值n和错误率fp以及Hash函数的个数k计算计数型Bloom filter中计数器位数m，生成初始计数型Bloom filter，初始计数型Bloom filter记为CBF0；b)用k个散列函数集h(x)＝{h₁(x),h₂(x)...h_i(x)...h_k(x)}将原始数据集插入到CBF0中；c)生成一个附加计数型Bloom filter，记为ACBF，它用于处理在同构计数型Bloom filter中查询到2个或以上的计数型Bloom filter中出现的同一元素，则将这种元素插入到该ACBF中；d)插入元素时，先到ACBF中查找，如查询到，则将该元素从ACBF中删除；如未查询到，则到同构计数型Bloom filter中查询，如查询到则不再插入；如在同构计数型Bloom filter中未查询到，则看是否有同构计数型Bloom filter未达到元素上限，如有则插入，否则生成一个新的同构计数型Bloom filter，并将元素插入到该计数型Bloom filter中；e)删除元素时，先到各同构计数型Bloom filter中查询元素，如在2个及以上的计数型Bloom filter中查询到，将该元素插入到ACBF中；否则将该元素从查询到的某同构计数型Bloom filter中删除，当某同构计数型Bloom filter中元素全部删除后则将该计数型Bloom filter删除；f)查询元素时，先到ACBF中查询，如查询到则返回无该元素；如附加计数型Bloom filter中没查询到，再到各个同构计数型Bloom filter中去查询，如在某个计数型Bloom filter查询到则返回有该元素。