An Analysis on the Error Probability of A Bloom Filter
SungYong Kim, Jihong Kim · 정보보호학회논문지 · 2014
ABSTRACT As the size of the data is getting larger and larger due to improvement of the telecommunication techniques, it would be main issues to develop and process the database. The bloom filt er used to lookup a particular element under the given set is very useful structure because of the space efficiency. In this paper, we introduce the error probabilities in Bloom filter. Especially, we derive the revised false positive rates of the Bloom filter using experimental method. Finally we analyze and compare the original false positive probability of the bloom fi lter used until now and the false decision probability proposed in this paper.Keywords: Bloom filter, False Positive Rate, False Negative Rate I.서 론 시스템 내에 저장된 캐쉬 메모리, 라우팅 테이블 등의 데이터 증가로 인하여, 데이터의 존재여부를 확인할 수 있는 인덱스로서 블룸필터를 자주 사용한다. 블룸필터는 개의 입력요소에 대하여 개의 해시함수 결과 값을 사이즈가 인 배열의 해당 비트에 ‘1’로 설정하는 것으로 데이터의 공간 활용에 매우 유용한 접수일(2014년 2월 3일), 수정일(1차: 2014년 7월 28일, 2차: 2014년 9월 12일), 게재확정일(2014년 9월 12일)* 이 논문은 2013학년도 세명대학교 교내학술연구비 지원에 의해 수행된 연구임†주저자, [email protected]‡교신저자, [email protected](Corresponding author)