Well, among the algorithms I studied on a course at Uni, there was one dealing with such things. Their recommended approach was to calculate the affinity index for each pair of users (which I think is your N * N method), and then based on this, determine which users are the closest user to.
Of course, you do not need to immediately recalculate the similarity indices for each change, only once in a while, while the search robot works. In fact, once you have calculated the starting index, you can use various heuristic methods to re-compromise for users who quickly change their preferences and much slower for those who rarely change them.
source share