Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
2011-05-03
2011-05-03
Malzahn, David H (Department: 2193)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
Reexamination Certificate
active
07937428
ABSTRACT:
A dynamic Bloom filter comprises a cascaded set of Bloom filters. The system estimates or guesses a cardinality of input items, selects a number of hash functions based on the desired false positive rate, and allocates memory for an initial Bloom filter based on the estimated cardinality and desired false positive rate. The system inserts items into the initial Bloom filter and counts the bits set as they are inserted. If the number of bits set in the current Bloom filter reaches a predetermined target, the system declares the current Bloom filter full. The system recursively generates additional Bloom filters as needed for items remaining after the initial Bloom filter is filled; items are checked to eliminate duplicates. Each of the set of Bloom filters is individually queried to identify a positive or negative in response to a query. When the system is configured such that the false positive rate of each successive Bloom filter is decreased by one half, the system guarantees a false positive rate of at most twice the desired false positive rate.
REFERENCES:
patent: 2003/0026268 (2003-02-01), Navas
patent: 2003/0208665 (2003-11-01), Peir et al.
patent: 2005/0033803 (2005-02-01), Vleet et al.
patent: 2005/0086520 (2005-04-01), Dharmapurikar et al.
patent: 2005/0108368 (2005-05-01), Mohan et al.
patent: 2005/0219929 (2005-10-01), Navas
patent: 2008/0155229 (2008-06-01), Beyer et al.
patent: 2008/0243800 (2008-10-01), Beyer et al.
patent: 2008/0243941 (2008-10-01), Beyer et al.
Using Bloom Filters by Maciej Ceglowski dated Apr. 8, 2004—O'REILLY PERL.COM The Source for Perl.
Michael Mizenmacher, “Compressed Bloom Filters”, Harvard University, IEEE/ACM Transactions on Networking, vol. 10, No. 5, Oct. 2002.
Patrick Reynolds and Amin Vahdat, “Efficient Peer-To-Peer Keyword Searching”, Dept of Computer Science, Duke University, 2003.
Purushottam Kulkarni, Prashant Shenoy, “Scalable Techniques for Memory-Efficient CDN Simulations”, Dept of Computer Science, Univeristy of Massachusetts, May 20-24, 2003.
Beyer Kevin Scott
Rajagopalan Sridhar
Zubiri Adriana
International Business Machines - Corporation
Malzahn David H
McSwain Marc D.
Shimokaji & Associates P.C.
LandOfFree
System and method for generating and using a dynamic bloom... 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 and using a dynamic bloom..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for generating and using a dynamic bloom... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2666948