《電子技術(shù)應(yīng)用》
您所在的位置：首頁 > 其他 > 設(shè)計應(yīng)用 > 面向缺失數(shù)據(jù)的布魯姆近似成員查詢算法
面向缺失數(shù)據(jù)的布魯姆近似成員查詢算法
2022年電子技術(shù)應(yīng)用第3期
吳佳雯1，王宇科2，裴書玉1，謝 鯤1，劉楚達(dá)3
1.湖南大學(xué) 信息科學(xué)與工程學(xué)院，湖南 長沙410082； 2.湖南大學(xué) 校園信息化建設(shè)與管理辦公室，湖南 長沙410082； 3.長沙航空職業(yè)技術(shù)學(xué)院，湖南 長沙410082
摘要： 隨著網(wǎng)絡(luò)的發(fā)展，越來越多的場景需要在不完整數(shù)據(jù)下進(jìn)行近似成員查詢，傳統(tǒng)成員查詢的布魯姆過濾器不能滿足上述要求。提出面向缺失數(shù)據(jù)的布魯姆近似查詢算法，先對高維不完整數(shù)據(jù)的缺失部分進(jìn)行預(yù)填充，通過PCA算法，將高維數(shù)據(jù)轉(zhuǎn)換到低維數(shù)據(jù)，使用局部敏感哈希函數(shù)與標(biāo)準(zhǔn)哈希函數(shù)結(jié)合的方式將低維數(shù)據(jù)存儲到布魯姆過濾器中。使用兩個真實數(shù)據(jù)集驗證了所提算法的功能，所提面向缺失數(shù)據(jù)的布魯姆近似查詢算法，能有效地解決存在缺失數(shù)據(jù)的近似成員查詢問題。
中圖分類號： TP393.0
文獻(xiàn)標(biāo)識碼： A
DOI：10.16157/j.issn.0258-7998.212468
中文引用格式： 吳佳雯，王宇科，裴書玉，等. 面向缺失數(shù)據(jù)的布魯姆近似成員查詢算法[J].電子技術(shù)應(yīng)用，2022，48(3)：78-82，87.
英文引用格式： Wu Jiawen，Wang Yuke，Pei Shuyu，et al. Approximate membership query algorithm for incomplete data based on Bloom filter[J]. Application of Electronic Technique，2022，48(3)：78-82，87.
Approximate membership query algorithm for incomplete data based on Bloom filter
Wu Jiawen1，Wang Yuke2，Pei Shuyu1，Xie Kun1，Liu Chuda3
1.College of Computer Science and Electronic Engineering，Hunan University，Changsha 410082，China； 2.Office of Information，Hunan University，Changsha 410082，China； 3.Changsha Aeronautical Vocational and Technical College，Changsha 410082，China
Abstract： More and more scenarios require approximate membership queries for incomplete query data, but traditional Bloom filters for membership queries cannot meet these requirements. An approximate membership query algorithm for incomplete data based on Bloom filter is proposed. It first preprocesses the missing parts of the high-dimensional incomplete data, then converts the high-dimensional data to the low-dimensional data based on PCA technique, and the low-dimensional data is stored in a Bloom filter by combining local sensitive hash functions with standard hash functions. Extensive experiments are conducted using two publicly real-world network performance datasets, and it shows that the proposed algorithm efficiently solves the approximate membership query problem for data with incomplete data. It is also necessary to enrich the means of filling in the missing parts in the data pre-processing. The proposed solution can effectively solve the approximate membership query problem for data with missingness.
Key words : Bloom filter；approximate membership query；query algorithm

0 引言

    標(biāo)準(zhǔn)的布魯姆過濾器(Bloom Filter，BF)[1]是一個空間效率很高的數(shù)據(jù)結(jié)構(gòu)，它可以表示集合并支持集合的成員查詢，快速判斷查詢元素是否在集合中。當(dāng)給定一個查詢元素e時，它被用來回答查詢元素是否在這個集合。一個標(biāo)準(zhǔn)的布魯姆構(gòu)造一個長度為m的比特位數(shù)組，初始化為0。在插入階段，它使用k個獨立的哈希函數(shù)h1(·)，…，hk(·)來計算插入元素在數(shù)組中對應(yīng)的k個哈希位置h1(e)%m，…，hk(e)%m，并將這k個哈希位置置位為“1”。在查詢階段，通過檢查是否所有的k個哈希位置都置位為“1”，來判斷元素是否在集合中。如果它們都置位為“1”，則認(rèn)為查詢元素e在集合S中；否則，則認(rèn)為查詢元素e不在集合S中。

    現(xiàn)有標(biāo)準(zhǔn)布魯姆過濾器通常用于常規(guī)的精確匹配的成員集合查詢(Exact-matching Membership Query，EMQ)，即：檢查查詢數(shù)據(jù)本身是否存儲在布魯姆過濾器，它是否是集合的一個成員。布魯姆過濾器作為一種空間精簡、查詢高效的支持成員集合查詢結(jié)構(gòu)，一直被廣泛用于各種實際應(yīng)用中[2-3]。在網(wǎng)絡(luò)領(lǐng)域應(yīng)用中，布魯姆過濾器可以用來存儲防火墻海量的黑名單數(shù)據(jù)[4]，以及在網(wǎng)站中進(jìn)行內(nèi)容去重等[5]。在大數(shù)據(jù)應(yīng)用中，例如HBase中使用布魯姆過濾器來減少代價高昂的I/O次數(shù)，提升數(shù)據(jù)庫查詢效率[6]。




本文詳細(xì)內(nèi)容請下載：http://theprogrammingfactory.com/resource/share/2000004008。




作者信息：

吳佳雯1，王宇科2，裴書玉1，謝  鯤1，劉楚達(dá)3

(1.湖南大學(xué) 信息科學(xué)與工程學(xué)院，湖南 長沙410082；

2.湖南大學(xué) 校園信息化建設(shè)與管理辦公室，湖南 長沙410082；

3.長沙航空職業(yè)技術(shù)學(xué)院，湖南 長沙410082)




wd.jpg

此內(nèi)容為AET網(wǎng)站原創(chuàng)，未經(jīng)授權(quán)禁止轉(zhuǎn)載。