It seems that it would pay out a lot for them to do a few simple heuristics by hand. For example: if just bought something do not show a thing from the same category. At most show a thing from accessories category, which I think they do.
Up until recently i used to work at a major Indian eCommerce and can confirm that most companies use a mix of the simple heuristics you suggest together with some data mining.
So, they would take your recent purchases, clicks, searches and wish listed products and recommended products from some accessory category or related products. ie. Traditional mining combined with heuristics.
It also helps to have separate widgets for similar products and for cross-sell products.
I always wondered why that happens at all but then I thought maybe it is because of their historic origins starting out as book seller - where showing another book after you bought a book makes absolute sense. While for refridgerators it makes no sense, they should put stuff in categories to distinguish that but then they are a super big company and I am single selftaught developer trying to make my living out of it.
