面向缺失数据的布鲁姆近似成员查询算法

论

文

赏

析

2022年电子技术应用第3期

吴佳雯1，王宇科2，裴书玉1，谢 鲲1，刘楚达3

1.湖南大学 信息科学与工程学院，湖南 长沙410082；2.湖南大学 校园信息化建设与管理办公室，湖南 长沙410082；3.长沙航空职业技术学院，湖南 长沙410082

摘要：   

随着网络的发展，越来越多的场景需要在不完整数据下进行近似成员查询，传统成员查询的布鲁姆过滤器不能满足上述要求。提出面向缺失数据的布鲁姆近似查询算法，先对高维不完整数据的缺失部分进行预填充，通过PCA算法，将高维数据转换到低维数据，使用局部敏感哈希函数与标准哈希函数结合的方式将低维数据存储到布鲁姆过滤器中。使用两个真实数据集验证了所提算法的功能，所提面向缺失数据的布鲁姆近似查询算法，能有效地解决存在缺失数据的近似成员查询问题。

关键词：

布鲁姆过滤器，近似成员查询，查询算法

0 引言：

标准的布鲁姆过滤器(Bloom Filter，BF)[1]是一个空间效率很高的数据结构，它可以表示集合并支持集合的成员查询，快速判断查询元素是否在集合中。当给定一个查询元素e时，它被用来回答查询元素是否在这个集合。一个标准的布鲁姆构造一个长度为m的比特位数组，初始化为0。在插入阶段，它使用k个独立的哈希函数h1(·)，…，hk(·)来计算插入元素在数组中对应的k个哈希位置h1(e)%m，…，hk(e)%m，并将这k个哈希位置置位为“1”。在查询阶段，通过检查是否所有的k个哈希位置都置位为“1”，来判断元素是否在集合中。如果它们都置位为“1”，则认为查询元素e在集合S中；否则，则认为查询元素e不在集合S中。

现有标准布鲁姆过滤器通常用于常规的精确匹配的成员集合查询(Exact-matching Membership Query，EMQ)，即：检查查询数据本身是否存储在布鲁姆过滤器，它是否是集合的一个成员。布鲁姆过滤器作为一种空间精简、查询高效的支持成员集合查询结构，一直被广泛用于各种实际应用中[2-3]。在网络领域应用中，布鲁姆过滤器可以用来存储防火墙海量的黑名单数据[4]，以及在网站中进行内容去重等[5]。在大数据应用中，例如HBase中使用布鲁姆过滤器来减少代价高昂的I/O次数，提升数据库查询效率[6]。

点击下方“阅读原文” 可下载完整版PDF文档！