While solving a practice exam, this is the question I could not answer. Any help is appreciated. I am new to hashing and have no idea how to solve this question.

Let $H$ be a $(0.15, 0.85, 0.9, 0.1)$-sensitive family of hash functions. Suppose we use 60 functions from $\cal{H}$ to sign the documents and apply an AND followed by OR construction using $b$ bands and $r$ rows within each band (hence $b$ and $r$ are whole numbers with $b \cdot r = 60$).

For any two documents to be considered a candidate pair, their signatures will need to match in all the $r$ rows of at least one band. For a similarity threshold of $0.15$, we would like the construction to yield a false positive rate of at most $0.05$ and for a similarity threshold of $0.85$, we would like the false negative rate to be at most $0.1$ - explain clearly whether or not this is possible, and if so, to provide appropriate values for $b$ and $r$ that will achieve the desired rates.

  • 1
    $\begingroup$ What did you try? Where did you get stuck? We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. We're not really looking for questions that are just the statement of an exercise-style or exam-style problem. If you're new to hashing, perhaps it would be better to study the course material on hashing, try to apply it to this problem, and then ask a question if you get stuck on some specific of it. $\endgroup$ – D.W. Nov 5 at 2:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.