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

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

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

groupId : int 
value : float

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

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

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

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

веселит,

Sören
7 голосов | спросил BuschnicK 6 PMpMon, 06 Apr 2009 13:25:41 +040025Monday 2009, 13:25:41

4 ответа


0

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

Ваша таблица представляет векторы, идентифицированные 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 раз.

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

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

ответил Daniel Brückner 6 PMpMon, 06 Apr 2009 23:14:22 +040014Monday 2009, 23:14:22
0

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

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

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

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

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

ответил fuzzy-waffle 7 AMpTue, 07 Apr 2009 05:47:44 +040047Tuesday 2009, 05:47:44
0

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

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

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

ответил FryGuy 7 AMpTue, 07 Apr 2009 06:21:38 +040021Tuesday 2009, 06:21:38
0
  

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

Если вы хотите использовать KNN на поплавках, используйте ---- +: = 0 =: + ---- для PostgreSQL и создайте btree_gist индекс.

  

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

<-> - это float8.

ответил Evan Carroll 8 AM00000080000005531 2018, 08:24:55

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132