基于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-稳定函数代替传统的随机和独立哈希函数来测量项目的局部化，并支持近似成员查询。

论文的其余部分组织如下：我们在第1节中介绍了PSDBF的设计。第2节给出了相关的工作。第3节给出结论。

1 P-稳定分布的布隆过滤器

一个P-稳定分布的布隆过滤器由一个m位数组组成，其中每个位最初都设置为0。设置L个P稳定分布函数，gi（1≤i≤L），将项散列成位，而不是散列表中原来的桶，以显著减少空间开销。每个散列函数的输入项gi根据散列计算映射到一个位。所有属于数据集S的项都可以插入到m位数组空间中，然后作为数据集S的汇总向量，以支持近似查询。当对项目q的近似查询请求到达时，我们执行相同的操作来插入一个项目通过哈希gi（q）（1≤i≤L）到L个比特位。如果L个比特位数均被设置为1，就认为项目q是数据集S在度量R的近似成员，例如p∈S，||p，q||≤R。具体流程如图1所示。

2 相关工作

近似成员查询因其广泛的应用而受到广泛的关注，Indyk和Motwani[1]引入局部敏感哈希已经成功应用在向量空间和字符串空间的近似查询中。现有的变体包括基于距离的散列[2]，多探测哈希[3]，基于距离的散列[2]将传统的哈希扩展到任意距离测量，从样本数据中进行统计观察。多功能探针哈希[3]多次检查散列桶，支持高维相似度搜索，提高基于统计分析的索引精度。大多数现有的基于哈希的设计必须消耗大量的存储空间来维护多个散列表，以提高近似查询的准确性。

另一个研究领域的目标是扩展空间效率的布隆过滤器，以支持近似查询与可接受的错误率。经过修饰的布隆过滤器[5]通过允许以产生随机假阴性为代价来删除某些假阳性，从而呈现假阳性和负率的组合。一种分区哈希方法[4]试图通过裁减每个项的哈希函数来设置比标准少得多的布隆过滤器位，从而降低布隆过滤器的误报率。

3 结论

在这篇论文中，我们提出了一个新的结构，称为PSDBF，以支持近似成员查询。PSDBF本质上是一种节省空间的布隆过滤器，但它取代了原来的哈希函数，P-稳定分布函数可以有效地保持散列项的接近性。与传统的哈希函数相比，基于P-稳定分布的哈希函数可以很大程度上减少错误率，提供更准确的成员查询，同时减少了存储空间的消耗。

参考文献

[1] Andoni A，Indyk P.Near-Optimal Hashing Algorithms for Approximate Nearest Neighbor in High Dimensions[C]//2006 47th Annual IEEE Symposium on Foundations of Computer Science （FOCS'06）.IEEE，2006.

[2] Athitsos V，Potamias M，Papapetrou P，et al.Nearest Neighbor Retrieval Using Distance-Based Hashing[C]//Data Engineering，2008.ICDE 2008.IEEE 24th International Conference on.IEEE，2008.

[3] Lv Q，Josephson W，Wang Z，et al.Multi-Probe LSH： Efficient Indexing for High-Dimensional Similarity Search[C]//Proceedings of the 33rd International Conference on Very Large Data Bases， University of Vienna，Austria，September 23-27，2007.VLDB Endowment，2007.

[4] Donnet B，Baynat B，Friedman T.Retouched bloom filters：allowing networked applications to trade off selected false positives against false negatives[C]//Proceedings of the 2006 ACM CoNEXT conference.ACM，2006：13.

[5] Hao F，Kodialam M，Lakshman T V.Building high accuracy bloom filters using partitioned hashing[J].ACM SIGMETRICS Performance Evaluation Review，2007，35（1）：277-288.