CPSC 461: Copyright © 2002 Katrin Becker 1998-2002 Last Modified October 20, 2001 09:25 PM

SIGNATURES REVIEW QUESTIONS

SHORT ANSWER QUESTIONS

1. [4 marks] In your own words, what is a Bloom Filter and why might you use one?

LONG QUESTIONS

1. (worth 15 total)
   We want to create a signature for a record file (containing 1 million records) to try and avoid having to search the file for records not found.
   The signature is 10K-bits long (10,000 bits)
   Each record is run through 4 hash functions to specify 4 bits to set:
   int H1 (Record* rec);
   int H2 (record* rec).
   What kind of data structure do we need for the signature? (an array of 10K elements such as bool Sig[10000] is unacceptable; i.e. the bits need to be packed with no wasted space)
   The buffer for the signature is
   unsigned char BUF[1250];
   Given your signature structure, write the algorithm to set the required bits in the signature for one record. Pseudo-code preferred. Each step must be explained.

-CPSC 461: Copyright©x 2000 Katrin Becker 1998-2002 Last ModifiedOctober 20, 2001-09:25 PM