Locality Sensitive Hashing (LSH): Practical and Illustrated Guide(pinecone.io)
pinecone.io
Locality Sensitive Hashing (LSH): Practical and Illustrated Guide
https://www.pinecone.io/learn/locality-sensitive-hashing/
5 comments
hmm. two thoughts:
1) i think it would be helpful to motivate by explaining that lsh queries are an approximation of doing pairwise jaccard similarity searches from the start. i think ullman does this.
2) it's a different approach to minhashing from the way i think about it. one hot encoding is not strictly necessary. all you need to do is for each round, randomly assign every shingle in the vocabulary an integer and take the lowest that is present in the document.
here's some concise python that will do it:
1) i think it would be helpful to motivate by explaining that lsh queries are an approximation of doing pairwise jaccard similarity searches from the start. i think ullman does this.
2) it's a different approach to minhashing from the way i think about it. one hot encoding is not strictly necessary. all you need to do is for each round, randomly assign every shingle in the vocabulary an integer and take the lowest that is present in the document.
here's some concise python that will do it:
def _chunk_text(m, chunksize=5):
len_m = len(m)
end = len_m - chunksize + 1 if len_m > chunksize else len_m
return set([m[i:i+chunksize] for i in range(end)])
def _minhash(s, siglen=20):
def minhash_k(chunks, k):
return min([mmh3.hash(x, k) for x in chunks])
return [minhash_k(_chunk_text(s), k) for k in range(siglen)]
I read the article but I could find nothing in the article that gives credit to Piotr Indyk, the inventor of Locality Sensitive Hashing and the math behind it. Give credit where it is due!
[deleted]
The article is well put together and nicely illustrated, though :)