I'm attempting to use minhash to generate clusters and similarities, and I am primarily using ideas from these resources.

The data that I am working with consists of interactions between users and items. There are 2.2M distinct users and 440M distinct items. Across all of the data, there are only 905M records, so it is very sparse.

In my approach, I am calculating H minimum hash values for each user by reordering the items (of which there are 440M). Users have a wide range of item interactions. The user with the most interactions as 2.5M interactions, the lowest is 1 interaction, the average is 403, and the median is only 26.

In google's doc about Google News, they recommend concatenating 2-4 keys (LSH) and doing this 10-20 times. I imagine this works well when a user has interacted with a smaller amount of items like news articles, but it is woefully low for what I am doing. When I test this number of keys for users that have 1,000+ interactions, many do not have any concatenated min has matches with another user. This is a problem because I can manually calculate cosine or jaccard similarity for some of these users and see an acceptable amount of similarity for my needs. I have found better results by not concatenating hash keys and using as many as 200.

For most of my hash key groups, there are around 2M distinct hash keys for the 2.24M users. As such, there is a fairly low amount of collision.

Do you guys have any tips for increasing the amount of clustering? I am considering using 1,000 hash keys and pairing users if they match on more than one. Thanks in advance.


One option is to change hashing functions to a function that is more likely to have collisions. For example, Pearson hashing is an 8-bit hash that will have far more collisions than more common hashing functions.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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