New Bloom Filter Structure Improves Processing Speed in Multiple Sets
Jungwon Lee · Journal of the Institute of Electronics and Information Engineers · 2021
다중 집합의 멤버쉽 쿼리는 네트워크 응용 프로그램에서 다양한 방식으로 사용된다. 기본 블룸 필터를 사용하여 다중 집합의 멤버쉽 쿼리를 수행할 경우, 집합의 수와 동일한 수만큼의 블룸필터를 사용해야 된다. 본 논문에서는 셀의 크기를 다중 집합의 수만큼으로 할당한 하나의 원형 블룸 필터를 사용하여 다중 집합의 각 원소가 속한 집합을 확인할 수 있는 구조를 제안한다. 또한, 제안하는 블룸 필터 구조는 프로그래밍과 쿼리 과정의 처리 속도를 감소시킨 구조이다. 실험 결과를 통해 블룸 필터의 크기가 증가할수록 거짓양성의 오류가 감소하고 멤버쉽 쿼리의 정확도가 기본 블룸 필터에 비해 0.9~1.4% 향상되었고 교집합에 있는 원소의 수가 증가할수록 블룸 필터 처리 속도가 감소함을 확인하였다.