中图分类号： 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