JIPS (한국정보처리학회)
Current Result Document :
| 한글제목(Korean Title) |
Approaches for Improving Bloom Filter-Based Set Membership Query |
| 영문제목(English Title) |
Approaches for Improving Bloom Filter-Based Set Membership Query |
| 저자(Author) |
HyunYong Lee
Byung-Tak Lee
|
| 원문수록처(Citation) |
VOL 15 NO. 03 PP. 0500 ~ 0569 (2019. 06) |
한글내용
(Korean Abstract) |
|
영문내용
(English Abstract) |
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%.
|
| 키워드(Keyword) |
Additional Filters
Bloom Filter
False Positive Probability
Hash Table
Processing Time
|
| 파일첨부 |
PDF 다운로드
|
