Mining of Massive Datasets

We begin our discussion of locality-sensitive hashing (LSH) with an examination of the problem of finding similar documents – those that share a lot of common text. We first show how to convert documents into sets in a way that lets us view textual similarity of documents as sets having a large overlap. A second key trick we need is minhashing, which is a way to convert large sets into much smaller representations, called signatures, that still enable us to estimate closely the Jaccard similarity of the represented sets. Finally, we see how to apply the bucketing idea inherent in LSH to the signatures. In Section 3.5 we begin our study of how to apply LSH to items other than sets. We consider the general notion of a distance measure that tells to what degree items are similar. Then, we consider the general idea of locality-sensitive hashing, and we see how to do LSH for some data types other than sets. We examine in detail several applications of the LSH idea. Finally, we consider some techniques for finding similar sets that can be more efficient than LSH when the degree of similarity we want is very high.