Как реализовать пересечение двух множеств (много данных)?

Как вы на мап-редьюс предлагаете решать данную задачу? Он не для этого.

Максимально до 500к (хотелось бы чтобы максимальный вариант хорошо отрабатывал а не средний.)
Пересечений там много. И сайтов самих тоже много.
>Либо попробовать сделать обратный индекс с сортировпнными сайтами, за один проход вычислять пересечение по сайту, все сайты раскидать по нодам, результат скидывать в БД для сортировки.
Поясните этот вариант.

Я думал о том чтобы вычислить один раз процент конкурентности для каждой пары сайтов. Но это таблица 60м х 60м записей

> Максимально до 500к (хотелось бы чтобы максимальный вариант хорошо отрабатывал а не средний.)

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

> Поясните этот вариант.

Возможно без обратного индекса будет лучше, если пересечений очень много, я бы попробовал так: сделать базу где все имена перевести в числа (keyvalue хранилище), далее сделать либу на C/C++ в которой реализовать загрузку и поиск, храним массив data[site_id] = [key3, key5] где ключи отсортированы, таким образом вес сайта можно вычислить за один проход, собираем результат сортируя. Возвращаем результат.

Если медленно - 2 улучшения:
1) Разбить все сайты на 10 (или более) кусков и раскидать на 10 ядер (машин), в теории ускориться в ~10 раз, делать запрос параллельно, собирать результаты и мержить.

2) Если пересечения не сильно большие, то можно использовать обратный индекс, это позволит не перебирать все сайты, а только те в которых есть ключи.

> Таблица большая (736к)
Я правильно понял что это результат по одному сайту?

Увы в данный момент реальных данных у меня нету так что я не могу сказать по поводу рапределения колличества ключей. Да конечно оптимайз хороший но для начала интересно реально ли решить в общем случае.

Получается струткра размером ~ 10 млн на 250к. А это слишком много даже для одного прохода.
+Ловим проблему с тем что после получения результатов (700к сайтов) с ними нужно строить таблицы.
В прочем я думаю это можно решить записав результат во временную mysql таблицу-кеш. И делать сортировки уже по ней. Потом её удалять.
Но это проход по 2.5 миллиардов элементов + выгрузка 700к в базу. Мне кажется что даже деля на 10 серверов мы не успеем это обработать за минуту.
(когдя я писал олимпиады на паскале цикл из 1-5млн элементов обрабатывался за секунду. Не думаю что с тех пор производительность систем изменилась на несколько порядков)

>> Таблица большая (736к)
>Я правильно понял что это результат по одному сайту?
Да конечно

> Получается струткра размером ~ 10 млн на 250к. А это слишком много даже для одного прохода.
10млн х 250к х 4b = 2300Gb, да и памяти не хило занимает.

На счет прохода, сейчас попробовал перебор, у меня ноутбук на одном ядре перебирает более 2000млн/сек, т.е. 8 ядерный сервер можно прикинуть ~32Gi/sec, 2500/32 = 78 сек полный перебор на одном сервере, хотя реальный код может быть сложнее.

Тут ещё вопрос, где вы столько рам возмете? это не дешево, а на диске хранить не вариант.

Тогда можно поискать какой-нибудь не точный поиск, где требуется меньше памяти, может какая-нибудь разбивка ключей по группам и оперировать уже небольшим кол-ом групп или т.п.

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

Алексей Солодкий: нет, но я не думаю что они помогут, а если запихать эти данные в граф, то памяти потребуется ещё больше.