System and method for generating a cache-aware bloom filter

Details System and method for generating a cache-aware bloom filter System and method for generating a cache-aware bloom filter

2008-06-05

2011-10-04

Ellis, Kevin (Department: 2187)

Electrical computers and digital processing systems: memory

Storage accessing and control

Memory configuring

C711S003000, C711S129000, C711S153000, C711S159000, C711S208000, C711S209000, C711S216000, C711SE12010

Reexamination Certificate

active

08032732

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.

REFERENCES:
patent: 6366994 (2002-04-01), Kalyur
patent: 6370622 (2002-04-01), Chiou et al.
patent: 6567815 (2003-05-01), Rubin et al.
patent: 7487317 (2009-02-01), Fedorova et al.
patent: 2003/0208665 (2003-11-01), Peir et al.
patent: 2006/0161607 (2006-07-01), Gustavson et al.
patent: 2006/0294311 (2006-12-01), Fu et al.
patent: 2008/0147714 (2008-06-01), Breternitz et al.
patent: 2008/0256094 (2008-10-01), Gupta et al.
patent: 2008/0313132 (2008-12-01), Hao et al.
Notice of Allowance from U.S. Appl. No. 11/614,790 dated May 13, 2009.

Affiliated with

Also associated with

Rating

System and method for generating a cache-aware bloom filter does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with System and method for generating a cache-aware bloom filter, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for generating a cache-aware bloom filter will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-4292551