0
$\begingroup$

I'm creating a website like where users will answer some yes/no questions set by me, up to them how many of those questions they want to answer. After a user submits his answer(s), he will be shown top 5 matches along with their match percentages. If two users have 10 common questions and their answers match for 8 of those questions then their match % will be 80%.

I can make this but my concern is about efficiency. A way of making this: If a user wants to see his top matches then match % (or match ratio) will be calculated for him vs every other user in the system. This will be stored in a temporary array. Array is sorted. Top 5 matches from the array are displayed.

Any less resource intensive way to calculate and show top matches?

Edit: If the top matches can be calculated without first calculating match percentages then i'm open to that.

$\endgroup$
4
  • $\begingroup$ Welcome to CS@SE. When tagging questions, please read the tag descriptions: I don't see any quality/error limit in your problem statement justifying tag approximation $\endgroup$
    – greybeard
    Jan 8 '20 at 7:09
  • $\begingroup$ (For best matches, why the detour via percentages?) $\endgroup$
    – greybeard
    Jan 8 '20 at 7:11
  • $\begingroup$ @greybeard Thanks. I've never learned approximation in CS but i'm open to approximate results if it makes doing ranking less resource intense. $\endgroup$
    – gom
    Jan 8 '20 at 7:54
  • $\begingroup$ @greybeard If the best matches can be calculated without first calculating match percentages then i'm open to that. $\endgroup$
    – gom
    Jan 8 '20 at 7:55
1
$\begingroup$

There is probably no algorithm that is significantly better than doing a pairwise comparison between all pairs of users.

You can, as you say, memoize (remember) the top-5 match for each user, so that you never have to recompute the top-5 for that user again in the future, but you'll still need to compare that user to each other user at least once. Basically, each time a new user appears, you compare them to all other users, to compute their top-5 matches (and update the top-5 matches of other users by adding this user to the top-5 lists of other users where appropriate).

That's basically the brute-force algorithm. I don't expect there to be an alternative that is better in practice.


In principle, there are a variety of methods. One method is to use a locality-sensitive hash. The simplest form of LSH is to choose a random subset of questions, then for each user extract their answers to those questions, hash that, and store the user in a bucket associated with the user's hash value. Then two users who are very similar have a decent chance of ending up in the same bucket. If you construct 100 such data structures, each with a different subset of questions, and if you choose the parameters right, you might have a decent chance of finding all of the top-5 matches in this way (along with some other extraneous matches, but those can be filtered out by doing a full comparison for each potential match). However, this is pretty fiddly with respect to parameters, and if people tend to answer only some of the questions, I suspect it won't perform that well in practice.

$\endgroup$
0
$\begingroup$

Regarding my "A way of making this",
Instead of array, building min heap of max 5 elements for top 5 matches is a better way. This heap will be populated when match %s are being calculated.

$\endgroup$

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.