发明名称 |
SYSTEM AND METHOD FOR GENERATING A CACHE-AWARE BLOOM FILTER |
摘要 |
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.
|
申请公布号 |
US2008243941(A1) |
申请公布日期 |
2008.10.02 |
申请号 |
US20080134125 |
申请日期 |
2008.06.05 |
申请人 |
INTERNATIONAL BUSINESS MACHINES CORPORATION |
发明人 |
BEYER KEVIN SCOTT;RAJAGOPALAN SRIDHAR |
分类号 |
G06F12/00 |
主分类号 |
G06F12/00 |
代理机构 |
|
代理人 |
|
主权项 |
|
地址 |
|