The patent badge is an abbreviated version of the USPTO patent document. The patent badge does contain a link to the full patent document.
The patent badge is an abbreviated version of the USPTO patent document. The patent badge covers the following: Patent number, Date patent was issued, Date patent was filed, Title of the patent, Applicant, Inventor, Assignee, Attorney firm, Primary examiner, Assistant examiner, CPCs, and Abstract. The patent badge does contain a link to the full patent document (in Adobe Acrobat format, aka pdf). To download or print any patent click here.
Patent No.:
Date of Patent:
Oct. 30, 2012
Filed:
Dec. 03, 2009
David C. Oliver, San Antonio, TX (US);
David C. Oliver, San Antonio, TX (US);
Google, Inc., Mountain View, CA (US);
Abstract
Systems and methods for Bloom filter compaction are described herein. A method embodiment includes reading a data corpus, inserting a plurality of data items from the data corpus into a Bloom filter, determining a number of the data items inserted, calculating a desired filter size based on the number, and constructing a compact Bloom filter based on the desired filter size. Another method embodiment includes generating a second bit vector from a first bit vector associated with a first Bloom filter, generating an empty second Bloom filter of a size based on the first bit vector, dividing the first Bloom filter's bit vector into a plurality of slices, and setting the second Bloom filter's bits based on an evaluation of the corresponding bits in each slice of the first Bloom filter's bit vector.