Par-BF: a parallel partitioned Bloom filter for dynamic data sets
文献类型：会议论文
| 作者 | Liu, Yi; Ge, Xiongzi; Du, David H.C.; Huang, Xiaoxia |
| 出版日期 | 2014 |
| 会议名称 | 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, LA |
| 英文摘要 | 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. © 2014 IEEE.(33 refs) |
| 收录类别 | EI |
| 语种 | 英语 |
| WOS记录号 | WOS:000382958000001 |
| 源URL | [http://ir.siat.ac.cn:8080/handle/172644/6049]  |
| 专题 | 深圳先进技术研究院_数字所 |
| 作者单位 | 2014 |
| 推荐引用方式 GB/T 7714 | Liu, Yi,Ge, Xiongzi,Du, David H.C.,et al. Par-BF: a parallel partitioned Bloom filter for dynamic data sets[C]. 见: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, LA. |
入库方式： OAI收割
来源：深圳先进技术研究院
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。