《電子技術應用》
您所在的位置：首頁 > 其他 > 設計應用 > 面向缺失數據的布魯姆近似成員查詢算法
面向缺失數據的布魯姆近似成員查詢算法
2022年電子技術應用第3期
吳佳雯1，王宇科2，裴書玉1，謝 鯤1，劉楚達3
1.湖南大學 信息科學與工程學院，湖南 長沙410082； 2.湖南大學 校園信息化建設與管理辦公室，湖南 長沙410082； 3.長沙航空職業(yè)技術學院，湖南 長沙410082
摘要： 隨著網絡的發(fā)展，越來越多的場景需要在不完整數據下進行近似成員查詢，傳統(tǒng)成員查詢的布魯姆過濾器不能滿足上述要求。提出面向缺失數據的布魯姆近似查詢算法，先對高維不完整數據的缺失部分進行預填充，通過PCA算法，將高維數據轉換到低維數據，使用局部敏感哈希函數與標準哈希函數結合的方式將低維數據存儲到布魯姆過濾器中。使用兩個真實數據集驗證了所提算法的功能，所提面向缺失數據的布魯姆近似查詢算法，能有效地解決存在缺失數據的近似成員查詢問題。
中圖分類號： TP393.0
文獻標識碼： A
DOI：10.16157/j.issn.0258-7998.212468
中文引用格式： 吳佳雯，王宇科，裴書玉，等. 面向缺失數據的布魯姆近似成員查詢算法[J].電子技術應用，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 引言

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

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




本文詳細內容請下載：http://m.ihrv.cn/resource/share/2000004008。




作者信息：

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

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

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

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




wd.jpg

此內容為AET網站原創(chuàng)，未經授權禁止轉載。