基于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.