Dual-load Bloom filter: Application for name lookup

Jungwon Lee, Hayoung Byun, Hyesook Lim

Research output: Contribution to journalArticlepeer-review

6 Scopus citations

Abstract

As a simple probabilistic data structure, a Bloom filter consumes a small amount of memory in efficiently dealing with a large set of data elements. Bloom filters stored in on-chip memories have been popularly used as pre-filters to minimize unnecessary off-chip memory accesses. This paper proposes an interesting variant of a Bloom filter, the dual-load Bloom filter (DLBF) and shows that the proposed DLBF can be effective for implementing a name lookup algorithm. While Bloom filters usually hold a single type of information, which is either the membership in a given set or the return values of elements, the proposed DLBF holds both the membership and the return values in a single Bloom filter. As one of the trie-based name lookup algorithms developed for named data networking, a path-compressed trie compresses each path in a name prefix trie by removing empty nodes with a single child. This type of trie should be designed to hold skip values to represent the numbers of removed nodes in addition to the name prefixes stored in each node. This paper shows that the proposed DLBF can hold the skip values and the name prefixes to implement a path-compressed trie in an on-chip memory. Simulation results show that the proposed name lookup structure improves search performance by 33% using a much smaller amount of memory than previous Bloom filter-based structures.

Original languageEnglish
Pages (from-to)1-9
Number of pages9
JournalComputer Communications
Volume151
DOIs
StatePublished - 1 Feb 2020

Keywords

  • Bloom filter
  • Dual-load Bloom filter
  • Name lookup
  • Name prefix trie
  • Named data networking
  • Path-compressed trie

Fingerprint

Dive into the research topics of 'Dual-load Bloom filter: Application for name lookup'. Together they form a unique fingerprint.

Cite this