ETRI-Knowledge Sharing Plaform

ENGLISH

성과물

논문 검색
구분 SCI
연도 ~ 키워드

상세정보

학술지 Approaches for Improving Bloom Filter-Based Set Membership Query
Cited 1 time in scopus Download 1 time Share share facebook twitter linkedin kakaostory
저자
이현용, 이병탁
발행일
201906
출처
Journal of Information Processing Systems, v.15 no.3, pp.550-569
ISSN
1976-913X
출판사
한국정보처리학회 (KIPS)
DOI
https://dx.doi.org/10.3745/JIPS.04.0116
협약과제
19ZK1100, 호남권 지역산업 기반 ICT융합기술 고도화 지원사업, 이길행
초록
We propose approaches for improving Bloom filter in terms of false positive probability and membership query speed. To reduce the false positive probability, we propose special type of additional Bloom filters that are used to handle false positives caused by the original Bloom filter. Implementing the proposed approach for a routing table lookup, we show that our approach reduces the routing table lookup time by up to 28% compared to the original Bloom filter by handling most false positives within the fast memory. We also introduce an approach for improving the membership query speed. Taking the hash table-like approach while storing only values, the proposed approach shows much faster membership query speed than the original Bloom filter (e.g., 34 times faster with 10 subsets). Even compared to a hash table, our approach reduces the routing table lookup time by up to 58%.
키워드
Additional filters, Bloom filter, False positive probability, Hash table, Processing time
KSP 제안 키워드
Bloom Filter, False positive, Filter-based, Hash table, Routing table lookup, Set membership, Table-like, membership query, processing time