In Chapter 3 of Mining of Massive Datasets, the basis of locality sensitive hashing is explained. They notably mention simhash for the cosine distance, where random hyperplanes are generated, and for each hyperplane, the projection of the vector to be hashed onto the hyperplane's normal is used for hashing the vector. They highlight that to instead measure euclidean distance, one can involve the use of a value $a$ as a segment length, used to split all hyperplane normals into some number of $a$-length segments. For each hyperplane, the segment into which the vector's projection falls into is used as its hash output. Hence the concatenation of this operation on each hyperplane generates a hash.

Yet a number of implementations, including what seems to be one of the most authoritative (falconn), do not use segments at all, and instead simply do a binary output depending on which side of the hyperplane the projection falls into. Why is this ? Why are segments not used ? What does the cosine distance have over the euclidean distance ?

  • 1
    $\begingroup$ Are you sure the implementations are for Euclidean and not Cosine distance? Cosine has some advantages over Euclidean but that is worthy of its own question. $\endgroup$ – Solomonoff's Secret Oct 15 '18 at 17:27
  • $\begingroup$ Unless I am misunderstanding your comment, that's what I highlight: They use cosine distance, not euclidean distance. See infolab.stanford.edu/~ullman/mmds/book.pdf, and github.com/FALCONN-LIB/FALCONN $\endgroup$ – alehresmann Oct 15 '18 at 18:21
  • $\begingroup$ @Solomonoff'sSecret $\endgroup$ – alehresmann Oct 15 '18 at 18:47
  • $\begingroup$ Okay, they use cosine distance. In that case the real question is why use cosine distance, not why use a certain version of LSH. $\endgroup$ – Solomonoff's Secret Oct 15 '18 at 19:29
  • $\begingroup$ @Solomonoff'sSecret You are right. I have fixed the question. $\endgroup$ – alehresmann Oct 15 '18 at 19:31

Cosine distance is common in Information Retrieval and other text-based scenarios because text is most easily represented as high dimensional sparse vectors in the word space. A few specific advantages of cosine distance over Euclidean distance are:

  • it is fast and simple - particularly, since vectors are sparse, only dimensions present in both vectors need be considered (if the vectors are pre-normalized);
  • it works well for vectors with moderate overlap in support, whereas in Euclidean distance coordinates outside of the support of one vector dominate;
  • it tends to work well with a wide variety of techniques - for example, in your question, LSH for cosine distance is simpler than LSH for Euclidean distance;
  • the magnitude of a vector, which usually corresponds to the length of the document, is not useful - note that cosine distance ignores length but Euclidean distance doesn't;
  • it is well-studied so it has momentum.

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.