Calculating match % and ranking according to that
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.