基于P-穩(wěn)定分布的布隆過濾器近似成員查詢算法

肖晨凱

摘要：布隆過濾器是近似成員查詢的主流算法之一。但是迄今為止還少有針對高維度、大規(guī)模數(shù)據(jù)的近似成員查詢算法。在這篇文章中，將提出一種新的基于P-穩(wěn)定分布的布隆過濾器算法（P-Stable Distributions Bloom Filter Algorithm ， PSDBF）。

關(guān)鍵詞：布隆過濾器;近似成員查詢;P穩(wěn)定分布

中圖分類號：TP311 文獻(xiàn)標(biāo)識碼：A 文章編號：1007-9416（2020）01-0102-02

0 引言

在許多實際和大規(guī)模的網(wǎng)絡(luò)應(yīng)用中，近似成員查詢比起精確查詢具有更廣泛的用途和作用。對于高維度、大規(guī)模數(shù)據(jù)精確匹配查詢的代價高昂。相反，近似成員查詢可以放寬對用戶請求的約束，使用戶在更短的時間內(nèi)獲得滿意的結(jié)果。

近似成員查詢旨在確定給定查詢q是否近似于數(shù)據(jù)集S。具體地說，給定一個d維度量空間U表示為（U，d），設(shè)這個空間中的點集合為S，給定一個常數(shù)參數(shù)R，如果p∈S并且||p，q||≤R，則查詢點q被認(rèn)為是近似成員。

本文提出的新的數(shù)據(jù)結(jié)構(gòu)，基于P-穩(wěn)定分布的布隆過濾器（PSDBF）可以快速有效的支持近似成員查詢查詢并且提高了查詢準(zhǔn)確度。PSDBF是一種按位向量的節(jié)省空間的結(jié)構(gòu)，它利用P-穩(wěn)定哈希函數(shù)將一個項散列到bucket中，其中bucket是二進(jìn)制位，從二進(jìn)制位向量可以指示最近項的存在。該設(shè)計是基于布隆過濾器可以借助不同的哈希函數(shù)將原始項映射到一個相對簡潔的存儲空間。因此，在保持項接近度的同時，用P-穩(wěn)定函數(shù)替換布隆過濾器中獨立且一致的散列函數(shù)是可行的。我們的貢獻(xiàn)總結(jié)如下：

我們提出了一個PSDBF結(jié)構(gòu)，用P-穩(wěn)定函數(shù)代替?zhèn)鹘y(tǒng)的隨機(jī)和獨立哈希函數(shù)來測量項目的局部化，并支持近似成員查詢。

論文的其余部分組織如下：我們在第1節(jié)中介紹了PSDBF的設(shè)計。第2節(jié)給出了相關(guān)的工作。第3節(jié)給出結(jié)論。

1 P-穩(wěn)定分布的布隆過濾器

一個P-穩(wěn)定分布的布隆過濾器由一個m位數(shù)組組成，其中每個位最初都設(shè)置為0。設(shè)置L個P穩(wěn)定分布函數(shù)，gi（1≤i≤L），將項散列成位，而不是散列表中原來的桶，以顯著減少空間開銷。每個散列函數(shù)的輸入項gi根據(jù)散列計算映射到一個位。所有屬于數(shù)據(jù)集S的項都可以插入到m位數(shù)組空間中，然后作為數(shù)據(jù)集S的匯總向量，以支持近似查詢。當(dāng)對項目q的近似查詢請求到達(dá)時，我們執(zhí)行相同的操作來插入一個項目通過哈希gi（q）（1≤i≤L）到L個比特位。如果L個比特位數(shù)均被設(shè)置為1，就認(rèn)為項目q是數(shù)據(jù)集S在度量R的近似成員，例如p∈S，||p，q||≤R。具體流程如圖1所示。

2 相關(guān)工作

近似成員查詢因其廣泛的應(yīng)用而受到廣泛的關(guān)注，Indyk和Motwani[1]引入局部敏感哈希已經(jīng)成功應(yīng)用在向量空間和字符串空間的近似查詢中。現(xiàn)有的變體包括基于距離的散列[2]，多探測哈希[3]，基于距離的散列[2]將傳統(tǒng)的哈希擴(kuò)展到任意距離測量，從樣本數(shù)據(jù)中進(jìn)行統(tǒng)計觀察。多功能探針哈希[3]多次檢查散列桶，支持高維相似度搜索，提高基于統(tǒng)計分析的索引精度。大多數(shù)現(xiàn)有的基于哈希的設(shè)計必須消耗大量的存儲空間來維護(hù)多個散列表，以提高近似查詢的準(zhǔn)確性。

另一個研究領(lǐng)域的目標(biāo)是擴(kuò)展空間效率的布隆過濾器，以支持近似查詢與可接受的錯誤率。經(jīng)過修飾的布隆過濾器[5]通過允許以產(chǎn)生隨機(jī)假陰性為代價來刪除某些假陽性，從而呈現(xiàn)假陽性和負(fù)率的組合。一種分區(qū)哈希方法[4]試圖通過裁減每個項的哈希函數(shù)來設(shè)置比標(biāo)準(zhǔn)少得多的布隆過濾器位，從而降低布隆過濾器的誤報率。

3 結(jié)論

在這篇論文中，我們提出了一個新的結(jié)構(gòu)，稱為PSDBF，以支持近似成員查詢。PSDBF本質(zhì)上是一種節(jié)省空間的布隆過濾器，但它取代了原來的哈希函數(shù)，P-穩(wěn)定分布函數(shù)可以有效地保持散列項的接近性。與傳統(tǒng)的哈希函數(shù)相比，基于P-穩(wěn)定分布的哈希函數(shù)可以很大程度上減少錯誤率，提供更準(zhǔn)確的成員查詢，同時減少了存儲空間的消耗。

參考文獻(xiàn)

[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，F(xiàn)riedman 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.