Fast Hash Function Logic Circuits for Counting Bloom Filters

Abstract

A Bloom Filter (BF) is an m-bit vector that can be used for fast data set membership queries. It has been found to be a useful tool for many applications in communications and computing. A Counting Bloom Filter (CBF) is an m-element vector that is a variant of a BF useful for supporting deletions of elements as well as count thresholding. Both a BF and a CBF can result in false positives (claiming an element is in a data set when that element has not yet been inserted into the data set). To ensure a low false positive probability in an application in which the inputs are not known in advance (which is the case with most practical applications), a BF or CBF must use hash functions with the two key properties of randomness and orthogonality. Randomness ensures that even highly skewed element distributions lead to uniform random distributions of elements in the CBF. Orthogonality ensures that the k hash functions do not "depend" on each other, thereby possibly leading to skewed data membership query replies. To ensure randomness and orthogonality, CBFs (and by extension BFs) are normally implemented in software using fairly sophisticated computation algorithms focused on cryptographic properties. However, many applications do not require cryptographic techniques, but instead would benefit from a fast and low overhead hardware implemented CBF. This thesis proposes fast and low overhead hardware circuits that can be used for the hash functions in CBFs used in non-cryptographic applications. The proposed circuits are based on XORShift operations, in which the bits of a number are shifted by a random amount and then exclusive-ORed with the unshifted version of that number. The proposed circuits are compared with previously proposed CBF (and BF) hash functions in terms of hardware delay and false positive rates. Simulation results show that the proposed circuits result in similar or slightly higher false positive rates that previous methods. However, the proposed circuits have significantly lower hardware delays that all other previously proposed hash function designs.

Bloom Filter (BF)는 데이터가 특정 집합에 포함되어 있는지 빠르게 확인할 수 있는 m-bit vector이다. 통신 및 컴퓨팅 분야에서 BF는 여러 곳에 활용되는 수단이다. Counting Bloom Filter (CBF)는 블룸 필터의 변형인 m-element vector이며 원소의 삭제 및 count thresholding을 지원한다. BF와 CBF 모두 false positive (어떤 원소가 데이터 집합에 삽입되지 않았는데 해당 원소가 존재한다고 보고하는 경우)가 발생할 수 있다. 어떤 입력이 주어질 지 모르는 상태에서, 낮은 false positive probability를 얻기 위해서 BF 및 CBF에 사용되는 해시 함수는 무작위성(randomness)과 상호독립성(orthogonality)의 특징을 가져야 한다. 무작위성은 불균형한 원소 분포가 주어져도 CBF에 균일하게 무작위로 분포될 수 있게 한다. 상호독립성은 k개의 해시 함수가 서로에 "의존(연관)"되지 않게 해서 불균형한 데이터라도 존재 여부 확인을 가능하게 한다. 무작위성과 상호독립성을 위해, CBF (및 BF의 변형들) 는 일반적으로 암호학적 성질에 기반한 다소 복잡한 계산 알고리즘으로 소프트웨어적으로 도입된다. 하지만, 대다수의 적용 예시는 암호학적인 기법이 불필요하고, 대신 빠르고 낮은 오버헤드의 하드웨어로 도입된 CBF가 효율적이다. 이 논문에서는 암호화가 필요없는 CBF의 해시 함수에 적용될 수 있는, 빠르고 낮은 오버헤드의 하드웨어 회로를 제안한다. 제안하는 회로는 입력값의 bit shift와 입력값과의 exclusive-OR 연산을 하는 XORShift를 기반으로 한다. 제안된 회로를 하드웨어 딜레이와 false positive rate의 관점에서, 이전에 제안된 CBF (와 BF) 해시 함수와 비교했다. 시뮬레이션 결과 제안된 회로는 다른 해시 함수들과 비슷하거나 약간 더 높은 false positive rate를 보였다. 그러나, 제안된 회로는 다른 해시 함수 디자인보다 매우 낮은 하드웨어 딜레이를 보였다. 따라서, 제안된 해시 함수 회로를 블룸 필터 및 변형된 블룸 필터에 적용하면 낮은 false positive probability와 빠른 해싱 성능을 얻을 수 있다.