Multi-Dimensional Bloom Filter: Design and Evaluation

Fei XU  Pinxin LIU  Jing XU  Jianfeng YANG  S.M. YIU  

IEICE TRANSACTIONS on Information and Systems   Vol.E100-D   No.10   pp.2368-2372
Publication Date: 2017/10/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.2016INP0022
Type of Manuscript: Special Section PAPER (Special Section on Security, Privacy and Anonymity in Computation, Communication and Storage Systems)
Category: Privacy, anonymity, and fundamental theory
Bloom Filter,  multi-dimensional matrix,  false positive rates,  

Full Text: PDF(431.6KB)
>>Buy this Article

Bloom Filter is a bit array (a one-dimensional storage structure) that provides a compact representation for a set of data, which can be used to answer the membership query in an efficient manner with a small number of false positives. It has a lot of applications in many areas. In this paper, we extend the design of Bloom Filter by using a multi-dimensional matrix to replace the one-dimensional structure with three different implementations, namely OFFF, WOFF, FFF. We refer the extended Bloom Filter as Feng Filter. We show the false positive rates of our method. We compare the false positive rate of OFFF with that of the traditional one-dimensional Bloom Filter and show that under certain condition, OFFF has a lower false positive rate. Traditional Bloom Filter can be regarded as a special case of our Feng Filter.