面向缺失数据的布鲁姆近似成员查询算法  

Approximate membership query algorithm for incomplete data based on Bloom filter

作　　者：吴佳雯 王宇科 裴书玉 谢鲲 刘楚达[3] Wu Jiawen;Wang Yuke;Pei Shuyu;Xie Kun;Liu Chuda(College of Computer Science and Electronic Engineering,Hunan University,Changsha 410082,China;Office of Information,Hunan University,Changsha 410082,China;Changsha Aeronautical Vocational and Technical College,Changsha 410082,China)

机构地区：[1]湖南大学信息科学与工程学院,湖南长沙410082 [2]湖南大学校园信息化建设与管理办公室,湖南长沙410082 [3]长沙航空职业技术学院,湖南长沙410082

出　　处：《电子技术应用》2022年第3期78-82,87,共6页Application of Electronic Technique

基　　金：国家自然科学基金项目(61972144);湖南省科教联合基金项目(2019JJ70031)。

摘　　要：随着网络的发展,越来越多的场景需要在不完整数据下进行近似成员查询,传统成员查询的布鲁姆过滤器不能满足上述要求。提出面向缺失数据的布鲁姆近似查询算法,先对高维不完整数据的缺失部分进行预填充,通过PCA算法,将高维数据转换到低维数据,使用局部敏感哈希函数与标准哈希函数结合的方式将低维数据存储到布鲁姆过滤器中。使用两个真实数据集验证了所提算法的功能,所提面向缺失数据的布鲁姆近似查询算法,能有效地解决存在缺失数据的近似成员查询问题。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.

关 键 词：布鲁姆过滤器 近似成员查询 查询算法 

分 类 号：TP393.0[自动化与计算机技术—计算机应用技术]