Architectural considerations for frequently matching similar users

Question

I've been trying to design a backend architecture to a SPA that satisfies the following:

• user constantly answer yes/no questions (ex: tinder swipe cards)
• The application calculates each user's similarity to one another solely based upon their answers
• Similarity between users should update as they answer more questions
• The application periodically prompts two active users with sufficient similarity to enter private chat
• The application will have up to 10 000 questions

Question:

Which architectural component should calculate/store/handle user similarity given that there are many concurrently active users constantly/frequently updating their answer set ?

Possible Approaches I've considered:

1. Create K-many tables (db). Periodically, the users are clustered (K-Means) into exactly one of the K tables. All users within a given table have sufficient similarity. The client requests two active users from a given table. sticking points: where/when is this calculation performed in the architecture and can only 1 user be re-clustered based upon their updates?
2. Calculate on-the-go (client and/or server worker threads) + caching. A client background process requests a list of random users and calculates this user's similarity to each. Caches matches. sticking points: If a user is answering at a high frequency, how often is this calculation performed? Furthermore does it scale?
3. Bitfield/bit representation of answers in the user model(server/db): Periodically the client requests a matched user. The server responds with a user by querying based upon the bitfield. sticking points: How does this scale to answering all 10 000 questions (ie: can a database store and query on such a large bit representation)?

Technology currently being used: Node/Express, PostgreSQL + ORM, Websockets.

Any insight with architectural patterns or database design or better approaches for this scenario would be greatly appreciated.

Research/Related:

• Jaccard Similarity
• How should a matchmaking app store matches for each user?
• DB structure for similarity detection
• Database design for comparing large lists of opinions

Answer 1

Great question. Unfortunately, I cannot answer it completely, but this is a bit much for a comment.

K-Means

The K-Means approach is probably the most realistic option under the following conditions:

• You know - or can calculate - a good value for k at any time you want to compare users.

• You're okay with comparing users only in certain intervals, not after every question.

• You have an idea for how to deal with users that have not answered all questions.

  If you view each user's answers as a Vector of {Yes, No, NotAnswered}^10k then users that have not answered many questions may be very similar, regardless of how much they agree on the answers they did give - especially if you have (k-1) "real" clusters.

If you want to change only one user, you can do that to a certain extent: Remove the user from its cluster and add it to the new closest cluster. Of course, over time the clusters' means will no longer reflect reality, so you need to update them (at which point of course, any user may be re-assigned).

Note: you can update the means as you go, of course, but you still need to re-cluster after a while, otherwise the clusters become increasingly useless.

Live Updates

Your second approach might give you a more accurate picture at any time, but it's infeasible for any non-trivial number of users. However, it might still work for you under certain conditions.

Since you're inviting users to chat, I assume you only really need to compare similarity between currently logged in users, which may or may not be reasonable.

Also, storing similarity values between each pair of users will likely not be possible, even if you restrict yourself to active users. However, you indicated that you might only store pairs that are matches. If this excludes most pairs, it might be workable. You can try to come up with a dynamic way to calculate the cut-off threshold to make sure you filter out most pairs.

You'll need a quick way to compare similarity. You can use a bit vector to represent Yes/No and another one to represent Answered/Unanswered. You can use those directly to check for equality, but not for similarity. You actually need to count equal bits. This will be an O(|Questions|) operation.

Local Sensitive Hashing

If you could come up with a hash function that puts reasonably similar answer-vectors into the same bucket, you could use that for coarse-grained matching and then only compare users in the same bucket.

Unfortunately, I don't see a how such a hash function could look like.