中圖分類號： 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

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