SQL эффективный запрос ближайшего соседа

Question

У меня возникают проблемы при создании эффективного SQL-запроса для решения следующей ситуации:

Предположим, у нас есть таблица с двумя столбцами

groupId : int 
value : float

Таблица огромна (несколько миллионов строк). Существует различное количество «значений» для «groupId» - скажем, от 100 до 50.000. Все значения с плавающей запятой больше или равны нулю, но в остальном не ограничены.

Для данного groupId запрос должен возвращать все другие группы, отсортированные по убыванию сходства, где «аналог» определяется как минимальное евклидово расстояние между всеми возможными парами из 30 значений в двух группах.

Именно это определение сходства и убивает меня. Я думаю, что для вычисления подобия, как определено выше, наивный алгоритм O (n ^ 2). Сейчас я ищу идеи, чтобы переопределить «сходство» или эффективную реализацию вышеизложенного. Я мог бы вообразить решение, включающее k-ближайшего соседа, что-то вроде геометрических ближайших соседей PostGis или, возможно, самый большой алгоритм общей подпоследовательности (хотя мне нужна «нечеткая» реализация последней, потому что «значения» вряд ли когда-либо будут сравниваться точно одинаково) .

В настоящее время мы находимся на mySQL, если это имеет значение.

ура

Sören

Answer 1

Не могли бы вы подтвердить, что я правильно понял вопрос?

Ваша таблица представляет векторы, идентифицированные groupId. Каждый вектор имеет размерность от 100 до 50000, но для измерения не определен порядок. То есть вектор из таблицы на самом деле является представителем класса эквивалентности.

Теперь вы определите сходство двух классов эквивалентности как минимальное евклидово расстояние проекций любых двух представителей классов эквивалентности до подпространства первых 30 измерений.

Примеры проекции на два измерения:

A = <1, 2, 3, 4>
B = <5, 6, 7, 8, 9, 10>

A представляет следующий класс эквивалентности векторов.

<1, 2, 3, 4>    <2, 1, 2, 3>    <3, 1, 2, 4>    <4, 1, 2, 3>
<1, 2, 4, 4>    <2, 1, 3, 2>    <3, 1, 4, 2>    <4, 1, 3, 2>
<1, 3, 2, 4>    <2, 3, 1, 4>    <3, 2, 1, 4>    <4, 2, 1, 3>
<1, 3, 4, 2>    <2, 3, 4, 1>    <3, 2, 4, 1>    <4, 2, 3, 1>
<1, 4, 2, 2>    <2, 4, 1, 3>    <3, 4, 1, 2>    <4, 3, 1, 2>
<1, 4, 3, 2>    <2, 4, 3, 1>    <3, 4, 2, 1>    <4, 3, 2, 1>

Проекция всех представителей этого класса эквивалентности на первые два измерения дает.

<1, 2>    <1, 3>    <1, 4>
<2, 1>    <2, 3>    <2, 4>
<3, 1>    <3, 2>    <3, 4>
<4, 1>    <4, 2>    <4, 3>

B представляет класс эквивалентности с 720 элементами. Проекция на первые два измерения дает 30 элементов.

< 5, 6>    < 5, 7>    < 5, 8>    < 5, 9>    < 5, 10>
< 6, 5>    < 6, 7>    < 6, 8>    < 6, 9>    < 6, 10>
< 7, 5>    < 7, 6>    < 7, 8>    < 7, 9>    < 7, 10>
< 8, 5>    < 8, 6>    < 8, 7>    < 8, 9>    < 8, 10>
< 9, 5>    < 9, 6>    < 9, 7>    < 9, 8>    < 9, 10>
<10, 5>    <10, 6>    <10, 7>    <10, 8>    <10,  9>

Таким образом, расстояние A и B является квадратным корнем из 8, потому что это минимальное расстояние двух векторов от проекций. Например, <3, 4> и <5, 6> дают это расстояние.

Итак, я прав в своем понимании проблемы?

Действительно наивный алгоритм для n векторов с m компонентами каждый должен был бы вычислять (n - 1) расстояния. Для каждого расстояния алгоритм будет рассчитывать расстояния m! / (м - 30)! проекция для каждого вектора. Таким образом, для 100 измерений (ваша нижняя граница) существует 2,65 * 10 ^ 32 возможных проекций для вектора. Для этого необходимо рассчитать около 7 * 10 ^ 64 расстояний между проекциями и найти минимум, чтобы найти расстояние двух векторов. А затем повторите это n раз.

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

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

Answer 2

Вот несколько хороших приближений:

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

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

Будет полезна дополнительная информация, например:

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

Answer 3

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

Если вы хотите использовать KNN для чисел с плавающей запятой, используйте модуль btree_gist для PostgreSQL и создайте индекс GIST.

Кроме того, для типов данных, для которых существует естественная метрика расстояния, btree_gist определяет оператор расстояния <-> и обеспечивает поддержку индекса GiST для поиска ближайших соседей с использованием этого оператора. Предоставляются операторы расстояния для int2, int4, int8, float4 , float8, метка времени с часовым поясом, метка времени без часового пояса, время без часового пояса, дата, интервал, oid и деньги.

float8 - это double precision.

Answer 4

Наивная версия будет выглядеть примерно так: (не выполняется через анализатор запросов)

select groupid, min(distance) as mindist
from
   (select other.groupid as groupid,
           min(abs(other.value - us.value)) as distance
    from g us
    join g other on other.groupid != us.groupid
    where us.groupid = ?)
order by mindist
group by groupid

Затем, чтобы воспользоваться признаками:

select groupid, min(abs(value - usvalue)) as mindist
from
   (select other.groupid as groupid,
           max(other.value) as value,
           us.value as usvalue
    from g us
    join g other on other.groupid != us.groupid and other.value <= us.value
    where us.groupid = ?

    union

    select other.groupid as groupid,
           min(other.value) as value,
           us.value as usvalue
    from g us
    join g other on other.groupid != us.groupid and other.value >= us.value
    where us.groupid = ?)
order by mindist
group by groupid

Это должно позволить MySQL использовать индекс для быстрого поиска ближайших соседей в соединении.

В этом могут быть ошибки, но, надеюсь, это поможет.