Быстрый поиск ближайшего соседа в 150-мерном пространстве

13

Я хочу создать базу данных, используя любую из возможных СУБД. В нем будет таблица с примерно 150 столбцами. Цель состоит в том, чтобы выполнить поиск ближайшего соседа некоторых других объектов. Так что это NNS в 150-мерном пространстве.

Я уже пытался использовать некоторые очевидные методы, такие как расстояния L1 или L2, но, конечно, это занимает много времени для таблиц с большим количеством строк. Также я попытался взглянуть на KD-дерево (заметьте, я не тестировал его) и PG-Strom, но они не являются хорошим решением для данных с большим количеством измерений.

Можно ли как-то улучшить скорость описанного поиска, используя математические методы (например, KD-дерево) или технические методы (например, PG-Strom)?

Я постараюсь использовать любую СУБД, позволяющую повысить скорость работы NNS. Но MySQL и PostgreSQL являются наиболее подходящей для меня СУБД.

database-design performance nearest-neighbor Дон-прог
источник
1
Это другие проблемы. Просто задайте еще один вопрос @ don-prog
Эван Кэрролл

Ответы:

17

PostgreSQL 9.6 с использованием cube

Сначала установите расширение куба

CREATE EXTENSION cube;

Теперь мы создадим некое n-мерное пространство с 100 000 точек в 50 измерениях. Кроме того, мы добавим индекс GIST.

CREATE TEMP TABLE space_nd
AS
  SELECT i, cube(array_agg(random()::float)) AS c
  FROM generate_series(1,1e5) AS i
  CROSS JOIN LATERAL generate_series(1,50)
    AS x
  GROUP BY i;

CREATE INDEX ON space_nd USING gist ( c );
ANALYZE space_nd;

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

WITH points AS (
  SELECT cube(array_agg(random()::float)) AS c
  FROM generate_series(1,50)
    AS x
)
SELECT i,
  pg_typeof(space_nd.c),
  pg_typeof(points.c),
  cube_distance(space_nd.c, points.c)
FROM space_nd
CROSS JOIN points
ORDER BY space_nd.c <-> points.c
LIMIT 5;

PostgreSQL 9.6+ поддерживает другие дистанционные операторы cube. Все из которых могут использовать индекс GIST, который мы создали. А именно,

a <-> b float8  Euclidean distance between a and b.
a <#> b float8  Taxicab (L-1 metric) distance between a and b.
a <=> b float8  Chebyshev (L-inf metric) distance between a and b.

Тем не менее, есть одна оговорка,

Чтобы людям было сложнее ломать вещи, существует ограничение в 100 на количество измерений кубов. Это устанавливается в cubedata.h, если вам нужно что-то большее.

Вы просите 150 размеров. Это может представлять незначительное осложнение.

Эван Кэрролл
источник
1
По cubedata.hмоему опыту, редактирование не работает после 130 измерений. Возможно, вы также можете изменить все doubles или float8s в расширении на float4, поскольку Postgres имеет ограничение на размер индекса для каждой строки, от которого вы можете отказаться, вдвое уменьшив количество байтов, которое вы используете для каждого числа. Я провел некоторое тестирование и таким образом получил больше измерений, и IIRC получил более 150, но я не совсем уверен.
Судо
У меня была такая
эксперт
2

Попробуйте сначала выполнить уменьшение размера (например, Анализ основных компонентов).

Тогда вы делаете NN в небольшом количестве измерений с более высокой производительностью.

При необходимости вы можете использовать Pl / R для выполнения PCA внутри postgres.

Робин Чаухан
источник
0

Взгляните на https://github.com/a-mma/AquilaDB, это база данных векторов для хранения векторов объектов вместе с метаданными JSON. Держите его вместе с РСУБД и используйте метаданные для поддержки перекрестных ссылок между данными.

а_ മ്മ
источник