CBFM：支持属性删减的布鲁姆过滤器矩阵多维元素查询算法

王勇，云晓春,2，王树鹏，王曦



CBFM：支持属性删减的布鲁姆过滤器矩阵多维元素查询算法

王勇1，云晓春1,2，王树鹏1，王曦1

（1. 中国科学院信息工程研究所北京 100093；2. 国家计算机网络应急技术处理协调中心北京 100029）

为了提升多维元素成员查询的灵活性和准确率，提出了一种新型索引结构CBFM(cutted Bloom filter matrix)。该索引方法通过独立属性布鲁姆过滤器笛卡尔乘积构建位矩阵，支持任意属性组合的多维元素成员查询，同时支持属性组合按需删减和属性加权，极大地提升内存空间利用率，降低查询误判率。理论分析证明相比于BFM(Bloom filter matrix)索引方法，CBFM具有更高的内存利用率。仿真实验表明，在分配内存相同的情况下，CBFM方法相比于其他方法，具有最低的查询误判率，特别在内存受限场景下，CBFM相比于BFM方法，查询误判率最大降低3个数量级，极大地提升了多维元素成员查询的准确率。

查询算法；多维元素成员查询；布鲁姆过滤器；位矩阵

1 引言

随着移动互联网、Web2.0等相关产业的快速发展，数据逐渐呈现出规模巨大化、类型多样化、流量高速化等大数据[1]特征，数据多维特征日趋明显，海量多维数据的存储、计算及实时分析为信息系统带来严峻的挑战。多维元素成员查询，是一种判断特定对象是否存在于目标数据集的重要手段，在数据集上进行全维度或部分维度查询并得到true/false的回答，广泛应用于分布式云存储[2~6]、网络监控及测量[7]等系统中。

在分布式云存储系统中，面对PB级数据量、数万属性的数据管理需求，Google BigTable[2]、HBase[3]等云存储系统，在进行数据操作之前，都需要在分布式节点上进行成员查询以便于定位目标数据；……