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

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

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

Теперь вы определяете подобие двух классов эквивалентности как минимальное евклидово расстояние проекций любых двух представителей классов эквивалентности на подпространство первых 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 раз.

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

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

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

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

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

Некоторая дополнительная информация была бы полезна, например:

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

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

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 использовать индекс для быстрого поиска ближайших соседей по соединению.

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

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

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

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

float8 is double precision.