Multi-Dimensional Bloom Filter: Design and Evaluation

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

doi:10.1587/transinf.2016INP0022

Multi-Dimensional Bloom Filter: Design and Evaluation

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

Full Text Views

0

Share
Cite this

Summary :

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.

Publication: IEICE TRANSACTIONS on Information Vol.E100-D No.10 pp.2368-2372

Publication Date: 2017/10/01

Publicized: 2017/07/21

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

Authors

Fei XU
  Renmin University
Pinxin LIU
  Renmin University
Jing XU
  Tsinghua University
Jianfeng YANG
  Renmin University
S.M. YIU
  The University of Hong Kong

Keyword

Bloom Filter, multi-dimensional matrix, false positive rates

Cite this

Copy

Fei XU, Pinxin LIU, Jing XU, Jianfeng YANG, S.M. YIU, "Multi-Dimensional Bloom Filter: Design and Evaluation" in IEICE TRANSACTIONS on Information, vol. E100-D, no. 10, pp. 2368-2372, October 2017, doi: 10.1587/transinf.2016INP0022.
Abstract: 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.
URL: https://globals.ieice.org/en_transactions/information/10.1587/transinf.2016INP0022/_p

Copy

@ARTICLE{e100-d_10_2368,
author={Fei XU, Pinxin LIU, Jing XU, Jianfeng YANG, S.M. YIU, },
journal={IEICE TRANSACTIONS on Information},
title={Multi-Dimensional Bloom Filter: Design and Evaluation},
year={2017},
volume={E100-D},
number={10},
pages={2368-2372},
abstract={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.},
keywords={},
doi={10.1587/transinf.2016INP0022},
ISSN={1745-1361},
month={October},}

Copy

TY - JOUR
TI - Multi-Dimensional Bloom Filter: Design and Evaluation
T2 - IEICE TRANSACTIONS on Information
SP - 2368
EP - 2372
AU - Fei XU
AU - Pinxin LIU
AU - Jing XU
AU - Jianfeng YANG
AU - S.M. YIU
PY - 2017
DO - 10.1587/transinf.2016INP0022
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E100-D
IS - 10
JA - IEICE TRANSACTIONS on Information
Y1 - October 2017
AB - 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.
ER -