One-hashing bloom filter
Lists
Only you see this
Abstract
Bloom filters are widely used in many network applications but the high computation cost limits the system performance. In this paper, we introduce a new variation of Bloom filter named One-Hashing Bloom Filter (OHBF) to solve the problem. OHBF requires only one base hash function plus a few simple operations to implement a Bloom filter. While keeping nearly the same theoretical false positive ratio as an ideal Bloom filter, OHBF significantly reduces the hash computation overhead. We show that the false positive performance of a standard Bloom filter implementation strongly relies on the selection of hash functions, even if these hash functions are considered good. In contrast, OHBF presents consistently better performance with a proven mathematical foundation. OHBF is ideal for high throughput and low latency applications. As OHBF is a fundamental technique in Bloom filter theory, it can be applied to many other Bloom filter variations, such as Counting Bloom Filter and Space-Code Bloom Filter.
BibTeX
@inproceedings{yang2015one,
author = {Tong Yang and Jianyuan Lu and Tong Yang and Yi Wang and Huichen Dai and Linxiao Jin and Haoyu Song and Bin Liu},
title = {{One-hashing bloom filter}},
booktitle = {Iwqos},
year = {2015},
doi = {10.1109/iwqos.2015.7404748},
}Loading related content...