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

肖晨凱

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

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

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

0 引言

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

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

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

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

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

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

一個(gè)P-穩(wěn)定分布的布隆過濾器由一個(gè)m位數(shù)組組成，其中每個(gè)位最初都設(shè)置為0。設(shè)置L個(gè)P穩(wěn)定分布函數(shù)，gi（1≤i≤L），將項(xiàng)散列成位，而不是散列表中原來的桶，以顯著減少空間開銷。每個(gè)散列函數(shù)的輸入項(xiàng)gi根據(jù)散列計(jì)算映射到一個(gè)位。所有屬于數(shù)據(jù)集S的項(xiàng)都可以插入到m位數(shù)組空間中，然后作為數(shù)據(jù)集S的匯總向量，以支持近似查詢。當(dāng)對(duì)項(xiàng)目q的近似查詢請(qǐng)求到達(dá)時(shí)，我們執(zhí)行相同的操作來插入一個(gè)項(xiàng)目通過哈希gi（q）（1≤i≤L）到L個(gè)比特位。如果L個(gè)比特位數(shù)均被設(shè)置為1，就認(rèn)為項(xiàng)目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]，多探測(cè)哈希[3]，基于距離的散列[2]將傳統(tǒng)的哈希擴(kuò)展到任意距離測(cè)量，從樣本數(shù)據(jù)中進(jìn)行統(tǒng)計(jì)觀察。多功能探針哈希[3]多次檢查散列桶，支持高維相似度搜索，提高基于統(tǒng)計(jì)分析的索引精度。大多數(shù)現(xiàn)有的基于哈希的設(shè)計(jì)必須消耗大量的存儲(chǔ)空間來維護(hù)多個(gè)散列表，以提高近似查詢的準(zhǔn)確性。

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

3 結(jié)論

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

參考文獻(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.