Paper Info
Title
Dual-load Bloom filter: Application for name lookup.
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.
Year
DOI
Venue
2020
10.1016/j.comcom.2019.12.029
Computer Communications
Keywords
Field
DocType
Bloom filter,Dual-load Bloom filter,Name prefix trie,Named data networking,Name lookup,Path-compressed trie
Bloom filter,Data structure,Computer science,Content based networking,Computer network,Arithmetic,Prefix,Probabilistic logic,Trie
Journal
Volume
ISSN
Citations 
151
0140-3664
0
PageRank 
References 
Authors
0.34
18
3
Name
Order
Citations
PageRank
Jungwon Lee189095.15
Ha Young Byun2141.58
Hyesook Lim330826.04