Suggested Final Project Topics

Why they’re worth studying: The mathematics behind locality-sensitive hash functions involves working

with random matrix theory and studying what happens if you project higher-dimensional objects into

lower-dimensional spaces. They’re also one of the more exciting theoretical primitives to have been devel-

oped in recent times, so looking into LSH might also introduce you to a number of other beautiful tech-

niques you wouldn’t have otherwise encountered.

Min-Hashing

How do you determine how similar two documents are? That’s a major question you’d need to answer if

you were trying to build a search engine or indexing huge amounts of text. One technique for solving this

problem involves techniques reminiscent of the cardinality estimation techniques we’ll cover: hash the

contents of the documents with different hash functions and take the smallest value produced. Amazingly,

these minimum hash values reveal a huge amount about the documents in question.