.png){kind=icon}
.png){kind=icon}
Return
Fast Dynamic Multiple-Set Membership Testing Using Combinatorial Bloom Filters
.png){kind=icon}
PRE
AI
DOI：10.1109/TNET.2011.2173351.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
In this paper, we consider the problem of designing a data structure that can perform fast multiple-set membership testing in deterministic time. Our primary goal is to develop a hardware implementation of the data structure that uses only embedded memory blocks. Prior efforts to solve this problem involve hashing into multiple Bloom filters. Such approach needs a priori knowledge of the number of elements in each set in order to size the Bloom filter. We use a single-Bloom-filter-based approach and use multiple sets of hash functions to code for the set (group) id. Since a single Bloom filter is used, it does not need a priori knowledge of the distribution of the elements across the different sets. We show how to improve the performance of the data structure by using constant-weight error-correcting codes for coding the group id. Using error-correcting codes improves the performance of these data structures especially when there are a large number of sets. We also outline an efficient hardware-based approach to generate the large number of hash functions that we need for this data structure. The resulting data structure, COMB, is amenable to a variety of time-critical network applications.
Keywords:
Bloom filter
computer networks
data structure
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
I
IF:
3.6
Papers:
4.4K
Citations:
9.5K