E.g. assume there's users, groups, and a many-to-many relationship between them. Assume there are millions of users, thousands of groups, and billions of user-group relationships.
Given a user, I want to sort the other users by the number of mutual groups between them. Doing it naively would be way too slow. I think caching the number of mutual groups for every pair of users is the most common approach, but caching n^2 user pairs would still be expensive (even if I only store non-zero pairs). I'm wondering if there's a probabilistic way to do this efficiently.
I'm not too familiar with Bloom filters, but if I generated Bloom filters for each user representing the groups they're in, I think I can use this for sorting users by number of mutual groups. I can XOR the given user's Bloom filters with every other user's Bloom filters, then sort by the number of 0s in the resulting bit arrays. If 2 users joined the identical groups, then they would have identical Bloom filters, so the XOR would produce all 0s. The issue is this would require a table scan, I don't think indexes would help.
Another way I can think of is abusing spatial indexes. E.g. if there are N groups, then in an N-dimensional space, a user's vector's nth value is 1 if they're in the nth group, and 0 otherwise. Then, I would use dimensionality reduction. 2 users with many mutual groups should be closer in the reduced space. The issue is:
- if I have many dimensions in the reduced space, it'll be expensive to store
- if I have few dimensions, there won't be enough signal to be useful
Is there a better algorithm for approximating the number of mutual things between users?