We share our admiration for a set of results called “locality sensitive hashing” by demonstrating a greatly simplified example that exhibits the spirit of the techniques.Locality sensitive hashing is awe inspiring in its originality, simplicity, beauty and effectiveness. In addition locality sensitive hashing is a remarkable technique as it works even when drastically abridged and simplified. In this paper (link to pdf) we give a description of conditions where the technique works and a heuristic argument why it works (using only elementary math).
Data Scientist and trainer at Win Vector LLC. One of the authors of Practical Data Science with R.