For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Multi-Dimensional Bloom Filter: Design and Evaluation
Fei XU Pinxin LIU Jing XU Jianfeng YANG S.M. YIU
IEICE TRANSACTIONS on Information and Systems
Publication Date: 2017/10/01
Online ISSN: 1745-1361
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.