.png){kind=icon}
.png){kind=icon}
Return
Par-BF: A parallel partitioned Bloom filter for dynamic data sets
.png){kind=icon}
PRE
AI
DOI：10.1177/1094342015618452.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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 10x to 14x and by 3x to 8x, respectively. Besides, through our proposed garbage collection policy, Par-BF consumes less than half of the memory usage of SBF.
Keywords:
Bloom filter
dynamic sets
Par-BF
false positive
fast matching
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
2.5
Papers:
1.1K
Citations:
1.3K