On reducing false positives of a Bloom filter in trie-based algorithms

Ju Hyoung Mun, Hyesook Lim

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

7 Scopus citations

Abstract

Many IP address lookup approaches employ Bloom filters to obtain a high-speed search performance. Especially, the search performance of trie-based algorithms can be significantly improved by adding Bloom filters, because Bloom filters can determine whether a node exists in a trie without accessing the trie. The false positive rate of a Bloom filter must be reduced to enhance the lookup performance. One important characteristic of a trie is that all the ancestors of a node are also stored. The proposed IP lookup algorithm utilizes this characteristic in reducing the false positive rate of a Bloom filter without increasing the Bloom filter size. When a Bloom filter produces a positive result for a node of a trie, we propose to check whether the ancestors of the node are also positives. Because Bloom filters have no false negatives, the negative of the ancestor means that the positive of the node is false. Simulation results show that the false positive rate is reduced up to 67% using the exact same amount of memory. The proposed approach can be applied to other trie-based algorithms employing Bloom filters.

Original languageEnglish
Title of host publicationANCS 2014 - 10th 2014 ACM/IEEE Symposium on Architectures for Networking and Communications Systems
PublisherAssociation for Computing Machinery
Pages249-250
Number of pages2
ISBN (Electronic)9781450328395
DOIs
StatePublished - 20 Oct 2014
Event10th ACM/IEEE Symposium on Architectures for Networking and Communications Systems, ANCS 2014 - Marina del Rey, United States
Duration: 20 Oct 201421 Oct 2014

Publication series

NameANCS 2014 - 10th 2014 ACM/IEEE Symposium on Architectures for Networking and Communications Systems

Conference

Conference10th ACM/IEEE Symposium on Architectures for Networking and Communications Systems, ANCS 2014
Country/TerritoryUnited States
CityMarina del Rey
Period20/10/1421/10/14

Keywords

  • Binary search on levels
  • Bloom filter
  • IP lookup

Fingerprint

Dive into the research topics of 'On reducing false positives of a Bloom filter in trie-based algorithms'. Together they form a unique fingerprint.

Cite this