Алгоритм поиска похожих пользователей через объединительную таблицу

Question

У меня есть приложение, в котором пользователи могут выбирать различные интересы из 300 возможных. Каждый выбранный интерес сохраняется в объединяющей таблице, содержащей столбцы user_id и Interest_id.

Обычные пользователи выбирают около 50 интересов из 300.

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

Сейчас я могу выполнить это, используя следующий запрос:

SELECT i2.user_id, count(i2.interest_id) AS count 
  FROM interests_users as i1, interests_users as i2
    WHERE i1.interest_id = i2.interest_id AND i1.user_id = 35
  GROUP BY i2.user_id
  ORDER BY count DESC LIMIT 20;

Однако выполнение этого запроса занимает около 500 миллисекунд с 10 000 пользователей и 500 000 строк в объединяемой таблице. Все индексы и параметры конфигурации базы данных были настроены в меру моих возможностей.

Я также пытался вообще избегать использования объединений, используя следующий запрос:

select user_id,count(interest_id) count
  from interests_users
    where interest_id in (13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,508)
  group by user_id 
  order by count desc 
  limit 20;

Но этот еще медленнее (~ 800 миллисекунд).

Как лучше всего сократить время, необходимое для сбора данных такого рода, до значения ниже 100 миллисекунд?

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

Answer 1

Код, который вы указали в качестве ответа, неверен. Храня счет в хэше, вы будете забывать многих пользователей, так как вы будете хранить только одного пользователя на общее количество. Например, если два пользователя имеют одинаковые интересы (или, по крайней мере, имеют одинаковое количество совпадающих интересов с текущим пользователем), ваша переменная t будет одинаковой, а первая просмотренная будет перезаписана второй.

Вот правильная версия кода, который вы разместили в качестве ответа. Это короче и более идиоматично и должно быть быстрее. Обратите внимание, что я использовал true и false вместо 1 и 0.

USERS_COUNT = 10_000
INTERESTS_COUNT = 500

users = Array.new(USERS_COUNT) { rand(100000)+100000 }

table = Array.new(INTERESTS_COUNT) do
  Array.new(USERS_COUNT) { rand(10) == 0 }
end

s = Time.now
cur_user = 0
cur_interests = table.each_index.select{|i| table[i][cur_user]}

scores = Array.new(USERS_COUNT) do |user|
  nb_match = cur_interests.count{|i| table[i][user] }
  [nb_match, users[user]]
end

scores.sort!

puts Time.now.to_f - s.to_f

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

Answer 2

SELECT DISTINCT TOP 20 b.user_id, SUM(1) OVER (PARTITION BY b.user_id) AS match
  FROM interests_users a
  LEFT OUTER JOIN interests_users b ON a.interest_id = b.interest_id AND b.user_id <> 35
 WHERE a.user_id = 35 AND b.user_id IS NOT NULL
 ORDER BY 2 DESC

Если вы строите хорошие индексы, у вас все будет хорошо.

Answer 3

Я действительно смог получить то, что искал, делая это в чистом Ruby.

Сначала я создаю двумерный массив, в котором каждый столбец является пользователем, а каждая строка представляет интерес. Каждое значение в массиве является 0 или 1 в зависимости от того, имеет ли текущий пользователь этот интерес. Этот массив хранится в памяти с функциями для добавления или изменения строк и столбцов.

Затем, когда я хочу подсчитать пользователей, имеющих схожие интересы с текущим пользователем, я складываю все столбцы для каждой строки, где столбец установлен в «1» для текущего пользователя. Это означает, что мне нужно перебрать 10000 столбцов и выполнить в среднем 50 операций добавления на столбец, а затем выполнить операцию сортировки в самом конце.

Вы можете догадаться, что это занимает очень много времени, но на моем компьютере это составляет около 50-70 миллисекунд (Core 2 Duo, 3 ГГц. Ruby 1.9.1) и около 110 миллисекунд на наших производственных серверах. Приятно то, что мне не нужно даже ограничивать набор результатов.

Вот код рубина, который я использовал для проверки моего алгоритма.

USERS_COUNT = 10_000
INTERESTS_COUNT = 500

users = []
0.upto(USERS_COUNT) { |u| users[u] = rand(100000)+100000 }

a = []
0.upto(INTERESTS_COUNT) do |r|
  a[r] = []
  0.upto(USERS_COUNT) do |c|
    if rand(10) == 0 # 10% chance of picking an interest
      a[r][c] = 1
    else
      a[r][c] = 0
    end
  end  
end

s = Time.now

countable_rows = []

a.each_index { |i| countable_rows << i unless a[i][0].zero? }

b = {}
0.upto(USERS_COUNT) do |c|
  t = 0
  countable_rows.each { |r| t+= a[r][c] }
  b[t] = users[c]
end
b = b.sort {|x,y| y[0] <=> x[0] }

puts Time.now.to_f - s.to_f

Первые несколько строк используются для создания имитируемого двумерного массива. Остальная часть программы запускает алгоритм, как я описал выше.

Приведенный выше алгоритм довольно хорошо масштабируется на некоторое время. Очевидно, что он не подходит для более 50 000 пользователей, но поскольку наш продукт разбивает сообщества на более мелкие группы, этот метод работает довольно хорошо (и намного быстрее, чем SQL).

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

Answer 4

То, о чем вы говорите, называется кластеризацией.

Кластеризация - сложная проблема, и для ее вычисления на лету требуется больше ресурсов, чем мы хотим сэкономить, боюсь, потому что полное вычисление - это O (N ² ).

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

Однако нам не нужно вычислять все это с нуля каждый раз. Я не смог выяснить развивающуюся картину (разумно) и как ее обновить.

Однако я могу понять, как кешировать результат!

UserId*  |  LinkedUserId*  |  Count
35       |  135            |  47
35       |  192            |  26

(Один индекс для UserId и другой для LinkedUserId, ограничение уникальности состоит в том, что никогда не должно быть 2 строк с одинаковой парой UserId / LinkedUserId)

Всякий раз, когда вам нужно получить группу для этого пользователя, сначала обратитесь к таблице кеша.

Теперь нам также нужно время от времени аннулировать некоторые записи в кэше: каждый раз, когда пользователь добавляет или удаляет интерес, он потенциально затрагивает всех пользователей, связанных с ним.

Когда пользователь добавляет запись, аннулирует все строки кэша пользователей, использующих этот интерес.

Когда пользователь удаляет запись, делает недействительными все строки кэша пользователей, связанных с ней.

Честно говоря, я не уверен, что это будет работать лучше.