Shameless self-promotion: in my Stack Overflow answer [1], I reference good introductory LSH papers [2-5].
In short, LSH is an algorithm that hashes points that are nearby in a feature space into the same bin with high probability. Contrast that with cryptographically secure hashes where the tiniest change in the input is designed to yield a completely different hash. The point is that, in domains like multimedia, you want to tolerate some distortions to your signal, e.g. microphone noise, blur, etc. These minor distortions shouldn't affect your characterization of the data, e.g. "is this a guitar", "is this a cat", etc.
The advantages are that it's simple to implement, and it has mathematically provable probability bounds and query complexity.
