System and method for generating a cache-aware bloom filter
US8032732B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Jun 5, 2008 |
| Grant date | Oct 4, 2011 |
| Priority date | — |
| Expiry date | May 21, 2030 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F17/10
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
A cache-aware Bloom filter system segments a bit vector of a cache-aware Bloom filter into fixed-size blocks. The system hashes an item to be inserted into the cache-aware Bloom filter to identify one of the fixed-size blocks as a selected block for receiving the item and hashes the item k times to generate k hashed values for encoding the item for insertion in the in the selected block. The system sets bits within the selected block with addresses corresponding to the k hashed values such that accessing the item in the cache-aware Bloom filter requires accessing only the selected block to check the k hashed values. The size of the fixed-size block corresponds to a cache-line size of an associated computer architecture on which the cache-aware Bloom filter is installed.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.