Par-BF: A parallel partitioned bloom filter for dynamic data sets

Yi Liu; Xiongzi Ge; David H Du; Xiaoxia Huang

doi:10.1109/DISCS.2014.5

Par-BF: A parallel partitioned bloom filter for dynamic data sets

Yi Liu, Xiongzi Ge, David H Du, Xiaoxia Huang

Computer Science and Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

5 Scopus citations

Abstract

Compared with a hash table, a Bloom Filter (BF) is more space-efficient for supporting fast matching though resulting in a controllable and acceptable false positive probability. The space size of the basic BF is predetermined based on the expected number of elements to be stored. However, we cannot predict the scale of a BF space for dynamic sets. The two existing solutions for supporting dynamic sets, Scalable BF (SBF) and Dynamic BF (DBF), still face some challenges on system performance and memory overhead.This paper presents a new BF for dynamic data sets, called Partitioned BF (Par-BF). Compared with DBF and SBF, the size and the range of the false positive probability can be calculated by a group of formulas to leverage a sweet spot between high-performance and low-overhead. Moreover, Par-BF supports parallel fast matching which can improve the overall throughput. From our trace-driven experimental results, the IOPS of Par-BF outperforms that of DBF and SBF from 6X to 10X, and from 2X to 4X, respectively. Meanwhile, through our proposed garbage collection policy, the memory overhead of Par-BF is less than half of the memory usage of SBF.

Original language	English (US)
Title of host publication	Proceedings of DISCS 2014
Subtitle of host publication	The 2014 International Workshop on Data-Intensive Scalable Computing Systems - Held in Conjuction with SC 2014: The International Conference for High Performance Computing, Networking, Storage and Analysis
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	1-8
Number of pages	8
ISBN (Electronic)	9781479970384
DOIs	https://doi.org/10.1109/DISCS.2014.5
State	Published - Apr 2 2014
Event	2014 International Workshop on Data-Intensive Scalable Computing Systems, DISCS 2014 - Held in Conjuction with the International Conference for High Performance Computing, Networking, Storage and Analysis, SC 2014 - New Orleans, United States Duration: Nov 16 2014 → …

Publication series

Name	Proceedings of DISCS 2014: The 2014 International Workshop on Data-Intensive Scalable Computing Systems - Held in Conjuction with SC 2014: The International Conference for High Performance Computing, Networking, Storage and Analysis

Other

Other	2014 International Workshop on Data-Intensive Scalable Computing Systems, DISCS 2014 - Held in Conjuction with the International Conference for High Performance Computing, Networking, Storage and Analysis, SC 2014
Country/Territory	United States
City	New Orleans
Period	11/16/14 → …

Bibliographical note

Publisher Copyright:
© 2014 IEEE.

Keywords

Bloom Filter
Par-BF
Parallel
dynamic sets

Publisher link

10.1109/DISCS.2014.5

Find It

Find It at U of M Libraries

Cite this

Liu, Y., Ge, X., Du, D. H., & Huang, X. (2014). Par-BF: A parallel partitioned bloom filter for dynamic data sets. In Proceedings of DISCS 2014: The 2014 International Workshop on Data-Intensive Scalable Computing Systems - Held in Conjuction with SC 2014: The International Conference for High Performance Computing, Networking, Storage and Analysis (pp. 1-8). Article 7079020 (Proceedings of DISCS 2014: The 2014 International Workshop on Data-Intensive Scalable Computing Systems - Held in Conjuction with SC 2014: The International Conference for High Performance Computing, Networking, Storage and Analysis). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/DISCS.2014.5

Par-BF: A parallel partitioned bloom filter for dynamic data sets. / Liu, Yi; Ge, Xiongzi; Du, David H et al.
Proceedings of DISCS 2014: The 2014 International Workshop on Data-Intensive Scalable Computing Systems - Held in Conjuction with SC 2014: The International Conference for High Performance Computing, Networking, Storage and Analysis. Institute of Electrical and Electronics Engineers Inc., 2014. p. 1-8 7079020 (Proceedings of DISCS 2014: The 2014 International Workshop on Data-Intensive Scalable Computing Systems - Held in Conjuction with SC 2014: The International Conference for High Performance Computing, Networking, Storage and Analysis).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Liu, Y, Ge, X, Du, DH & Huang, X 2014, Par-BF: A parallel partitioned bloom filter for dynamic data sets. in Proceedings of DISCS 2014: The 2014 International Workshop on Data-Intensive Scalable Computing Systems - Held in Conjuction with SC 2014: The International Conference for High Performance Computing, Networking, Storage and Analysis., 7079020, Proceedings of DISCS 2014: The 2014 International Workshop on Data-Intensive Scalable Computing Systems - Held in Conjuction with SC 2014: The International Conference for High Performance Computing, Networking, Storage and Analysis, Institute of Electrical and Electronics Engineers Inc., pp. 1-8, 2014 International Workshop on Data-Intensive Scalable Computing Systems, DISCS 2014 - Held in Conjuction with the International Conference for High Performance Computing, Networking, Storage and Analysis, SC 2014, New Orleans, United States, 11/16/14. https://doi.org/10.1109/DISCS.2014.5

Liu Y, Ge X, Du DH, Huang X. Par-BF: A parallel partitioned bloom filter for dynamic data sets. In Proceedings of DISCS 2014: The 2014 International Workshop on Data-Intensive Scalable Computing Systems - Held in Conjuction with SC 2014: The International Conference for High Performance Computing, Networking, Storage and Analysis. Institute of Electrical and Electronics Engineers Inc. 2014. p. 1-8. 7079020. (Proceedings of DISCS 2014: The 2014 International Workshop on Data-Intensive Scalable Computing Systems - Held in Conjuction with SC 2014: The International Conference for High Performance Computing, Networking, Storage and Analysis). doi: 10.1109/DISCS.2014.5

Liu, Yi ; Ge, Xiongzi ; Du, David H et al. / Par-BF : A parallel partitioned bloom filter for dynamic data sets. Proceedings of DISCS 2014: The 2014 International Workshop on Data-Intensive Scalable Computing Systems - Held in Conjuction with SC 2014: The International Conference for High Performance Computing, Networking, Storage and Analysis. Institute of Electrical and Electronics Engineers Inc., 2014. pp. 1-8 (Proceedings of DISCS 2014: The 2014 International Workshop on Data-Intensive Scalable Computing Systems - Held in Conjuction with SC 2014: The International Conference for High Performance Computing, Networking, Storage and Analysis).

@inproceedings{541aa9f70e8c4a9381f2eebb8cd327ba,

title = "Par-BF: A parallel partitioned bloom filter for dynamic data sets",

abstract = "Compared with a hash table, a Bloom Filter (BF) is more space-efficient for supporting fast matching though resulting in a controllable and acceptable false positive probability. The space size of the basic BF is predetermined based on the expected number of elements to be stored. However, we cannot predict the scale of a BF space for dynamic sets. The two existing solutions for supporting dynamic sets, Scalable BF (SBF) and Dynamic BF (DBF), still face some challenges on system performance and memory overhead.This paper presents a new BF for dynamic data sets, called Partitioned BF (Par-BF). Compared with DBF and SBF, the size and the range of the false positive probability can be calculated by a group of formulas to leverage a sweet spot between high-performance and low-overhead. Moreover, Par-BF supports parallel fast matching which can improve the overall throughput. From our trace-driven experimental results, the IOPS of Par-BF outperforms that of DBF and SBF from 6X to 10X, and from 2X to 4X, respectively. Meanwhile, through our proposed garbage collection policy, the memory overhead of Par-BF is less than half of the memory usage of SBF.",

keywords = "Bloom Filter, Par-BF, Parallel, dynamic sets",

author = "Yi Liu and Xiongzi Ge and Du, {David H} and Xiaoxia Huang",

note = "Publisher Copyright: {\textcopyright} 2014 IEEE.; 2014 International Workshop on Data-Intensive Scalable Computing Systems, DISCS 2014 - Held in Conjuction with the International Conference for High Performance Computing, Networking, Storage and Analysis, SC 2014 ; Conference date: 16-11-2014",

year = "2014",

month = apr,

day = "2",

doi = "10.1109/DISCS.2014.5",

language = "English (US)",

series = "Proceedings of DISCS 2014: The 2014 International Workshop on Data-Intensive Scalable Computing Systems - Held in Conjuction with SC 2014: The International Conference for High Performance Computing, Networking, Storage and Analysis",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "1--8",

booktitle = "Proceedings of DISCS 2014",

}

TY - GEN

T1 - Par-BF

T2 - 2014 International Workshop on Data-Intensive Scalable Computing Systems, DISCS 2014 - Held in Conjuction with the International Conference for High Performance Computing, Networking, Storage and Analysis, SC 2014

AU - Liu, Yi

AU - Ge, Xiongzi

AU - Du, David H

AU - Huang, Xiaoxia

PY - 2014/4/2

Y1 - 2014/4/2

N2 - Compared with a hash table, a Bloom Filter (BF) is more space-efficient for supporting fast matching though resulting in a controllable and acceptable false positive probability. The space size of the basic BF is predetermined based on the expected number of elements to be stored. However, we cannot predict the scale of a BF space for dynamic sets. The two existing solutions for supporting dynamic sets, Scalable BF (SBF) and Dynamic BF (DBF), still face some challenges on system performance and memory overhead.This paper presents a new BF for dynamic data sets, called Partitioned BF (Par-BF). Compared with DBF and SBF, the size and the range of the false positive probability can be calculated by a group of formulas to leverage a sweet spot between high-performance and low-overhead. Moreover, Par-BF supports parallel fast matching which can improve the overall throughput. From our trace-driven experimental results, the IOPS of Par-BF outperforms that of DBF and SBF from 6X to 10X, and from 2X to 4X, respectively. Meanwhile, through our proposed garbage collection policy, the memory overhead of Par-BF is less than half of the memory usage of SBF.

AB - Compared with a hash table, a Bloom Filter (BF) is more space-efficient for supporting fast matching though resulting in a controllable and acceptable false positive probability. The space size of the basic BF is predetermined based on the expected number of elements to be stored. However, we cannot predict the scale of a BF space for dynamic sets. The two existing solutions for supporting dynamic sets, Scalable BF (SBF) and Dynamic BF (DBF), still face some challenges on system performance and memory overhead.This paper presents a new BF for dynamic data sets, called Partitioned BF (Par-BF). Compared with DBF and SBF, the size and the range of the false positive probability can be calculated by a group of formulas to leverage a sweet spot between high-performance and low-overhead. Moreover, Par-BF supports parallel fast matching which can improve the overall throughput. From our trace-driven experimental results, the IOPS of Par-BF outperforms that of DBF and SBF from 6X to 10X, and from 2X to 4X, respectively. Meanwhile, through our proposed garbage collection policy, the memory overhead of Par-BF is less than half of the memory usage of SBF.

KW - Bloom Filter

KW - Par-BF

KW - Parallel

KW - dynamic sets

UR - http://www.scopus.com/inward/record.url?scp=84940745992&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84940745992&partnerID=8YFLogxK

U2 - 10.1109/DISCS.2014.5

DO - 10.1109/DISCS.2014.5

M3 - Conference contribution

AN - SCOPUS:84940745992

T3 - Proceedings of DISCS 2014: The 2014 International Workshop on Data-Intensive Scalable Computing Systems - Held in Conjuction with SC 2014: The International Conference for High Performance Computing, Networking, Storage and Analysis

SP - 1

EP - 8

BT - Proceedings of DISCS 2014

PB - Institute of Electrical and Electronics Engineers Inc.

Y2 - 16 November 2014

ER -

Par-BF: A parallel partitioned bloom filter for dynamic data sets

Abstract

Publication series

Other

Bibliographical note

Keywords

Publisher link

Find It

Other files and links

Fingerprint

Cite this