블룸필터의 오류 확률에 대한 분석
An Analysis on the Error Probability of A Bloom Filter
0
조회
0
다운로드
3
인용
0
참고문헌
키워드
초록
최근 정보통신 기술의 발달로 인하여 데이터의 양이 점차 증가하고 있으며, 이에 대한 처리와 관련된 연구가 활발히진행되고 있다. 주어진 집합 내에 특정 개체의 존재여부를 알기위해 사용되고 있는 블룸필터는 데이터의 공간 활용에매우 유용한 구조이다. 본 논문에서는 블룸필터에서 발생될 수 있는 오류 확률을 소개한다. 특히 실험실적 분석방법에의하여 수정된 긍정오류 확률에 대한 일반식을 유도한다. 마지막으로 지금까지 사용되고 있는 블룸필터에 대한 긍정오류확률식과 이에 대한 관련논문을 이용하여 비교, 분석한다.
Abstract
As the size of the data is getting larger and larger due to improvement of the telecommunication techniques, it would bemain issues to develop and process the database. The bloom filter used to lookup a particular element under the given set isvery 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 andcompare the original false positive probability of the bloom filter used until now and the false decision probability proposed inthis paper.
참고문헌 (7)
- B. Bloom, "Space", Time Trade-offs in Hash Coding with Allowable Errors, 1970, pp.13(7), 422~426
- A. Broder, "Network Applications of Bloom Filters : A Survey", Internet Mathematics, I(4), pp.485~509 (2004)
- ON THE FALSE-POSITIVE RATE OF BLOOM FILTERS, "P. Bose", School of Computers Science, Carleton University, ~ (2004)
- K. Christensen, "A new analysis of the false positive rate of a Bloom filter", Information Processing Letters, 110, pp.944~949 (2010)
- O. Rottenstreich, "The Bloom Paradox: When not to Use a Bloom Filter?", INFOCOM, pp.1638~1646 (2012)
- L. Fan, "Summary Cache : A Scalable Wide-Area Web Cache Sharing Protocol", IEEE, 2000, pp.8(3), 281~293
- R. P. Laufer, "A Generalized Bloom Filter to Secure Distributed Network Applications", Computer Networks, 55(8), pp.1804~1819 (2011)