IEICE TRANSACTIONS on Information
Multi-Dimensional Bloom Filter: Design and Evaluation
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
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
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://global.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 -
English
