基于P-稳定分布的布隆过滤器近似成员查询算法

肖晨凯

摘要：布隆过滤器是近似成员查询的主流算法之一。但是迄今为止还少有针对高维度、大规模数据的近似成员查询算法。在这篇文章中，将提出一种新的基于P-稳定分布的布隆过滤器算法（P-Stable Distributions Bloom Filter Algorithm ， PSDBF）。

关键词：布隆过滤器;近似成员查询;P稳定分布

中图分类号：TP311 文献标识码：A 文章编号：1007-9416（2020）01-0102-02

0 引言

在许多实际和大规模的网络应用中，近似成员查询比起精确查询具有更广泛的用途和作用。对于高维度、大规模数据精确匹配查询的代价高昂。相反，近似成员查询可以放宽对用戶请求的约束，使用户在更短的时间内获得满意的结果。

近似成员查询旨在确定给定查询q是否近似于数据集S。具体地说，给定一个d维度量空间U表示为（U，d），设这个空间中的点集合为S，给定一个常数参数R，如果p∈S并且||p，q||≤R，则查询点q被认为是近似成员。

本文提出的新的数据结构，基于P-稳定分布的布隆过滤器（PSDBF）可以快速有效的支持近似成员查询查询并且提高了查询准确度。PSDBF是一种按位向量的节省空间的结构，它利用P-稳定哈希函数将一个项散列到bucket中，其中bucket是二进制位，从二进制位向量可以指示最近项的存在。该设计是基于布隆过滤器可以借助不同的哈希函数将原始项映射到一个相对简洁的存储空间。因此，在保持项接近度的同时，用P-稳定函数替换布隆过滤器中独立且一致的散列函数是可行的。我们的贡献总结如下：

我们提出了一个PSDBF结构，用P-稳定函数代替传统的随机和独立哈希函数来测量项目的局部化，并支持近似成员查询。……