다중 집합의 처리 속도를 향상시킨 새로운 블룸 필터 구조 (New Bloom Filter Structure Improves Processing Speed in Multiple Sets)

서지정보

· 발행기관 : 대한전자공학회
· 수록지 정보 : 전자공학회논문지 / 58권 / 8호 / 17 ~ 23페이지
· 저자명 : 이정원

초록

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

영어초록

Membership query of multiple sets is used in various ways in network applications. When multiple sets membership query is performed using a standard Bloom filter, a Bloom filter of the same size as the number of a set must be used. This paper proposes a method to determine the set to which each element of multiple sets belongs by using a single Bloom filter with multi-bit. The proposed structure implements a Bloom filter with a cell size proportional to the number of multiple sets and proposes a structure that enables multiple sets membership query while reducing the operation of the Bloom filter through single programming and querying. Simulation result shows that false positive error decreased and accuracy increased as the sizing factor of the Bloom filter increased. In addition, it was confirmed that the processing speed of the Bloom filter operation decreases as the number of elements in the intersection increases.

참고자료

· 없음