Have a look at Google's MinHash algorithm. While it's a probabilistic solution, You can run it as a mapreduce and will at no point need to have the full data s

Have a look at Google's MinHash algorithm. While it's a probabilistic solution, You can run it as a mapreduce and will at no point need to have the full data set in memory/on a single machine. So it does scale pretty well. http://www2007.org/papers/paper570.pdf http://www2007.org/papers/paper570.pdf EDIT: I see you changed your comment to include "no full graph recalcuation". Incremental recos are possible to do with minhash but I think you can't solve decay of old data easily.