Алгоритм для поиска похожих элементов на основе пользовательской активности

Если же у меня 1000000 товаров, то связей будет 1000000000000

Не будет у тебя столько связей, матрица сильна разрежена.

Пересечений должно быть относительно мало. Если товаров не слишком много можно не держать отдельную таблицу, а делать выборку из оформленных заказов. Можно также хранить или делать выборку по категориям, а не самим товарам.

Матрица конечно разрежена, но потенциально столько счетчиков и есть

И если таким образом считать не товары, а страницы форума, то вполне себе столько будет. Как минимум, после первого визита гугла.

1. Возможно это не задача для базы с табличками 2. Не нужно ничего хранить - можно выбрать из таблички прошлых покупок в квадрате.

Ну, в классических базах это я и не собираюсь хранить, скорее сделаю специализированного демона на сишке. Тут вопрос в том - что хранить? «Прошлые покупки в квадрате» - это уже само по себе дофига данных, а в случае форума - вообще гигантский объем данных.

Я так понял критерием «похожести» какого-либо одного товара с другим будет наличие в прошлом оплаченного заказа, который содержит оба товара? Эти заказы-то уже где-то хранятся, логично просто делать выборку оттуда.

это НЕ простая задача, если разряженная матрица не устраивает (реальный крупный магазин, или в общем случае большая выборка - где флага «купили вместе» станет недостаточно). см. https://en.wikipedia.org/wiki/Association_rule_learning, там есть «алгоритмы поиска» (offline)

ну а простое решение уже привели - достать из базы все транзакции с товаром Х, достать из транзакций товары Y, как-нибудь отранжировать, закэшировать; для средних обьёмов должно быть достаточно..

Прошлые покупки в квадрате - это уже само по себе дофига данных

Кажется, ты не понял. Квадрат хранить не нужно, а покупки всё равно уже храняться, скорее всего.