文獻(xiàn)標(biāo)識(shí)碼: A
DOI:10.16157/j.issn.0258-7998.212468
中文引用格式: 吳佳雯,王宇科,,裴書(shū)玉,,等. 面向缺失數(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.
0 引言
標(biāo)準(zhǔn)的布魯姆過(guò)濾器(Bloom Filter,BF)[1]是一個(gè)空間效率很高的數(shù)據(jù)結(jié)構(gòu),,它可以表示集合并支持集合的成員查詢,,快速判斷查詢?cè)厥欠裨诩现小.?dāng)給定一個(gè)查詢?cè)豦時(shí),,它被用來(lái)回答查詢?cè)厥欠裨谶@個(gè)集合,。一個(gè)標(biāo)準(zhǔn)的布魯姆構(gòu)造一個(gè)長(zhǎng)度為m的比特位數(shù)組,初始化為0,。在插入階段,,它使用k個(gè)獨(dú)立的哈希函數(shù)h1(·),…,,hk(·)來(lái)計(jì)算插入元素在數(shù)組中對(duì)應(yīng)的k個(gè)哈希位置h1(e)%m,,…,hk(e)%m,,并將這k個(gè)哈希位置置位為“1”,。在查詢階段,通過(guò)檢查是否所有的k個(gè)哈希位置都置位為“1”,,來(lái)判斷元素是否在集合中,。如果它們都置位為“1”,則認(rèn)為查詢?cè)豦在集合S中,;否則,,則認(rèn)為查詢?cè)豦不在集合S中。
現(xiàn)有標(biāo)準(zhǔn)布魯姆過(guò)濾器通常用于常規(guī)的精確匹配的成員集合查詢(Exact-matching Membership Query,,EMQ),,即:檢查查詢數(shù)據(jù)本身是否存儲(chǔ)在布魯姆過(guò)濾器,它是否是集合的一個(gè)成員,。布魯姆過(guò)濾器作為一種空間精簡(jiǎn),、查詢高效的支持成員集合查詢結(jié)構(gòu),一直被廣泛用于各種實(shí)際應(yīng)用中[2-3],。在網(wǎng)絡(luò)領(lǐng)域應(yīng)用中,,布魯姆過(guò)濾器可以用來(lái)存儲(chǔ)防火墻海量的黑名單數(shù)據(jù)[4],以及在網(wǎng)站中進(jìn)行內(nèi)容去重等[5],。在大數(shù)據(jù)應(yīng)用中,,例如HBase中使用布魯姆過(guò)濾器來(lái)減少代價(jià)高昂的I/O次數(shù),提升數(shù)據(jù)庫(kù)查詢效率[6],。
本文詳細(xì)內(nèi)容請(qǐng)下載:http://forexkbc.com/resource/share/2000004008,。
作者信息:
吳佳雯1,王宇科2,,裴書(shū)玉1,,謝 鯤1,,劉楚達(dá)3
(1.湖南大學(xué) 信息科學(xué)與工程學(xué)院,湖南 長(zhǎng)沙410082,;
2.湖南大學(xué) 校園信息化建設(shè)與管理辦公室,,湖南 長(zhǎng)沙410082;
3.長(zhǎng)沙航空職業(yè)技術(shù)學(xué)院,,湖南 長(zhǎng)沙410082)