Вычисление парного косинусного сходства между довольно большим числом векторов в Bigquery

Question

У меня есть таблица id_vectors, которая содержит id и соответствующие им coordinates.Каждое из coordinates представляет собой повторяющиеся поля с 512 элементами внутри него.

Я ищу парное косинусное сходство между всеми этими векторами, например, если у меня три ids 1,2 и 3, тогда яищу таблицу, где у меня есть косинусное сходство между ними (на основе расчета с использованием 512 координат), как показано ниже:

id1   id2   similarity
 1     2      0.5
 1     3      0.1
 2     3      0.99

Теперь в моей таблице у меня 424 970 уникальных ID и соответствующие им 512-мерные координаты,Это означает, что в основном мне нужно создать (424970 * 424969/2) уникальную пару идентификаторов и вычислить их сходство.

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

#standardSQL
with pairwise as
(SELECT t1.id as id_1, t1.coords as coord1, t2.id as id_2, t2.coords as coord2
FROM `project.dataset.id_vectors` t1
inner join `project.dataset.id_vectors` t2
on t1.id < t2.id)

SELECT id_1, id_2, ( 
  SELECT 
    SUM(value1 * value2)/ 
    SQRT(SUM(value1 * value1))/ 
    SQRT(SUM(value2 * value2))
  FROM UNNEST(coord1) value1 WITH OFFSET pos1 
  JOIN UNNEST(coord2) value2 WITH OFFSET pos2 
  ON pos1 = pos2
  ) cosine_similarity
FROM pairwise

Но после 6 часов работы я обнаружил следующее сообщение об ошибке Query exceeded resource limits. 2.2127481953201417E7 CPU seconds were used, and this query must use less than 428000.0 CPU seconds.

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

Итак, я попробовал следующий запрос:

SELECT t1.id as id_1, t1.coords as coord1, t2.id as id_2, t2.coords as coord2
FROM `project.dataset.id_vectors` t1
inner join `project.dataset.id_vectors` t2
on t1.id < t2.id

Но на этот раз запрос не мог быть выполнен, и я обнаружил следующее сообщение: Error: Quota exceeded: Your project exceeded quota for total shuffle size limit. For more information, see https://cloud.google.com/bigquery/troubleshooting-errors.

Затем япопытался создать таблицу еще меньшего размера, просто создав пары комбинаций идентификаторов и убрав из нее координаты, используя следующий запрос:

SELECT t1.id as id_1, t2.id as id_2
FROM `project.dataset.id_vectors` t1
inner join `project.dataset.id_vectors` t2
on t1.id < t2.id

И снова мой запрос заканчивается сообщением об ошибке Query exceeded resource limits. 610104.3843576935 CPU seconds were used, and this query must use less than 3000.0 CPU seconds. (error code: billingTierLimitExceeded)

Я полностью понимаю, что это огромный запрос, и моя остановка - моя квота выставления счетов.

Я спрашиваю, есть ли способ выполнить запрос более разумным способом?чтобы я не превышал ни resourceLimit, shuffleSizeLimit, ни billingTierLimit?

Answer 1

Быстрая идея: вместо того, чтобы объединять таблицу с избыточными координатами, вам лучше просто создать простую таблицу пар (id1, id2), так что тогда вы «оденете» соответствующие идентификаторы в их векторы координат, имея два дополнительных соединения.на dataset.table.id_vectors

Ниже приведен краткий пример того, как это может выглядеть:

#standardSQL
WITH pairwise AS (
  SELECT t1.id AS id_1, t2.id AS id_2
  FROM `project.dataset.id_vectors` t1
  INNER JOIN `project.dataset.id_vectors` t2
  ON t1.id < t2.id
)
SELECT id_1, id_2, ( 
  SELECT 
    SUM(value1 * value2)/ 
    SQRT(SUM(value1 * value1))/ 
    SQRT(SUM(value2 * value2))
  FROM UNNEST(a.coords) value1 WITH OFFSET pos1 
  JOIN UNNEST(b.coords) value2 WITH OFFSET pos2 
  ON pos1 = pos2
  ) cosine_similarity
FROM pairwise t
JOIN `project.dataset.id_vectors` a ON a.id = id_1
JOIN `project.dataset.id_vectors` b ON b.id = id_2

Очевидно, это работает на небольшом фиктивном наборе, как вы можете видеть ниже:

#standardSQL
WITH `project.dataset.id_vectors` AS (
  SELECT 1 id, [1.0, 2.0, 3.0, 4.0] coords UNION ALL
  SELECT 2, [1.0, 2.0, 3.0, 4.0] UNION ALL
  SELECT 3, [2.0, 0.0, 1.0, 1.0] UNION ALL
  SELECT 4, [0, 2.0, 1.0, 1.0] UNION ALL 
  SELECT 5, [2.0, 1.0, 1.0, 0.0] UNION ALL
  SELECT 6, [1.0, 1.0, 1.0, 1.0]
), pairwise AS (
  SELECT t1.id AS id_1, t2.id AS id_2
  FROM `project.dataset.id_vectors` t1
  INNER JOIN `project.dataset.id_vectors` t2
  ON t1.id < t2.id
)
SELECT id_1, id_2, ( 
  SELECT 
    SUM(value1 * value2)/ 
    SQRT(SUM(value1 * value1))/ 
    SQRT(SUM(value2 * value2))
  FROM UNNEST(a.coords) value1 WITH OFFSET pos1 
  JOIN UNNEST(b.coords) value2 WITH OFFSET pos2 
  ON pos1 = pos2
  ) cosine_similarity
FROM pairwise t
JOIN `project.dataset.id_vectors` a ON a.id = id_1
JOIN `project.dataset.id_vectors` b ON b.id = id_2

с результатом

Row id_1    id_2    cosine_similarity    
1   1       2       1.0  
2   1       3       0.6708203932499369   
3   1       4       0.819891591749923    
4   1       5       0.521749194749951    
5   1       6       0.9128709291752769   
6   2       3       0.6708203932499369   
7   2       4       0.819891591749923    
8   2       5       0.521749194749951    
9   2       6       0.9128709291752769   
10  3       4       0.3333333333333334   
11  3       5       0.8333333333333335   
12  3       6       0.8164965809277261   
13  4       5       0.5000000000000001   
14  4       6       0.8164965809277261   
15  5       6       0.8164965809277261     

Итак, попробуйте свои реальные данные и посмотрим, как они будут работать для вас: o)

И ... очевидно, вы должны предварительно создать / материализоватьpairwise таблица

Другая идея оптимизации заключается в том, чтобы предварительно рассчитать значения SQRT(SUM(value1 * value1)) в вашем project.dataset.id_vectors - это может сэкономить достаточно ресурсов процессора - это должна быть простая настройка, поэтому я оставляю это вам: o)