Par-BF: A parallel partitioned Bloom filter for dynamic data sets
Authors:
- 28 July 2016
- journal article
- research article
- Published by SAGE Publications in The International Journal of High Performance Computing Applications
- Vol. 30 (3) , 259-275
Abstract
Compared with a hash table, a Bloom filter (BF) is more space efficient for supporting fast matching through 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 space scale of a BF for dynamic sets. It is still challenging for the two existing solutions, scalable BF (SBF) and dynamic BF (DBF), to manipulate dynamic data sets with low memory overhead but achieving high performance. This article presents a partitioned BF (Par-BF) for dynamic data sets. Compared with DBF and SBF, Par-BF is able to leverage a sweet spot between high performance and low overhead by a group of formulas to support fast concurrent matching. Specifically, the size and the range of the false positive probability in Par-BF can be deliberately derived. From our trace-driven experimental results, the input/output operations per second of Par-BF outperforms that of DBF and SBF by 10× to 14× and by 3× to 8×, respectively. Besides, through our proposed garbage collection policy, Par-BF consumes less than half of the memory usage of SBF.Keywords
This publication has 36 references indexed in Scilit:
- Combinatorics2018
- Benchmarking cloud serving systems with YCSB2010
- HadoopDBProceedings of the VLDB Endowment, 2009
- Redundancy in network traffic2009
- Scalable Bloom FiltersInformation Processing Letters, 2007
- An Improved Construction for Counting Bloom Filters2006
- Network Applications of Bloom Filters: A SurveyInternet Mathematics, 2004
- Spectral bloom filters2003
- Implementing a relational database by means of specialzed hardwareACM Transactions on Database Systems, 1979
- Space/time trade-offs in hash coding with allowable errorsCommunications of the ACM, 1970