How would you technically implement a matching algorithm like OkCupid?

Don't know about OKC but eHarmony apparently uses SVD: http://en.wikipedia.org/wiki/Singular_value_decomposition (and has a patent on their application of SVD to dating services, which is somewhat controversial)

First, don't forget that they can limit the search space to people that match your preferences like location and age. So this might yield just a few thousand people. It might be feasible to do very expensive algorithms on all of them. But let's say you're more indiscriminate and live in a big metro area. So now we have a few hundred thousand to get through. OKCupid isn't much like a nearest neighbor search. We are not matching two people together, we are matching requirements to people. Consider that one person might be super picky and their potential partner might be less discriminating. Their score must be some combination of how they both fit each other's requirements, not how much they were like one another. The requirement-to-person closeness might be nearest neighbor, but I doubt it... Thinking of each question like a dimension isn't helpful -- there is no such thing as "close" or "far". You either match or you don't. To me this suggests a bitwise operation. The community has helpfully ranked all the questions for us. So we just need to place the answers in aggregate popularity order, and do some bitwise operations, and boom, we already have a rough compatibility ranking. This probably doesn't even take that much data. Somewhere between 64 and 256 bits. Then, for people who match you highly, or for people you happen to be viewing, they can go for more accuracy and match the long-tail questions, weighted on the importances you entered. By the way, I have noticed that OKCupid is pretty relaxed about giving you perfect results, which is how it should be. Try this experiment; move the location of your profile to a totally different city. Your matches will be abysmal in quality -- almost random. A few hours later, they are back to being very good. Presumably there is some batching or clustering happening asynchronously, with cached results. To keep you interested, all OKCupid has to do is keep showing you profiles. They never claim that their results are absolutely complete, or make you wait for the almighty algorithm to complete.

Bipartite graph matching is one possible way: http://en.wikipedia.org/wiki/Matching_%28graph_theory%29 There's also likely a dual between graph algorithms (e.g., matching) and matrix algorithms (SVD) given that a graph could be expressed a matrix.

I don't really know, but I worked on a problem once where we pretty much used brute force for lack of a mathematics background. Possibly useful: the curse of dimensionality [1] means that if you use some kind of distance function, as you add more questions, it becomes less useful to put people in clusters. It's more efficient to start with questions that rule out most people all by themselves (e.g. geography and simple filters), before scoring the rest. [1] http://en.wikipedia.org/wiki/Curse_of_dimensionality

A bit off topic, but if you want some OkCupid data to test your algorithms on, check out: http://www.infochimps.com/datasets/personality-insights-okcupid-questions-and-answers-by-gender-age

You could also hold a sorted key-value store of ORDERED-ANSWERS|SCORE as keys and "ORDERED-ANWERS" as values (e.g. leveldb). There would then be 0 calculation on a person changing their answer-profile (i.e. answering a new question, changing an answer, etc), 0 calculation on adding/removing a new person, and 0 calculation and minimal IO on result look-up. This calc table would never need to change until a new question was added (don't even need to do anything on question removal). The only costs would be calculation on adding a new question to the system (which could be pre-padded) and db disk space. The value side of the key-value store would require a quick single-join look-up to match actual people. If you were to asynchronously pre-cache a result set on any answer-profile update, you would be left with only the cache look-up IO on request. I've used this successfully for recommendation engines (e.g. sorting products in online interfaces to elevate items each individual is "most likely to buy").