Início / dba / Perguntas / 163207
Accepted
konstantin_doncov
Asked: 2017-02-04 21:35:05 +0800 CST

Pesquisa rápida do vizinho mais próximo no espaço de 150 dimensões

  • 772

Eu quero criar um banco de dados usando qualquer um dos RDBMS possíveis. Terá uma tabela com aproximadamente 150 colunas. O objetivo é realizar a busca do vizinho mais próximo de alguns outros objetos. Então é um NNS no espaço de 150 dimensões.

Já tentei usar alguns métodos óbvios como distâncias L1 ou L2 mas claro que demora muito para tabelas com muitas linhas. Também tentei olhar para o KD-tree (note que não testei) e PG-Strom, mas eles não são uma boa solução para dados com muitas dimensões.

Posso de alguma forma melhorar a velocidade da pesquisa descrita usando métodos matemáticos (como KD-tree) ou métodos técnicos (como PG-Strom)?

Vou tentar usar qualquer RDBMS que permita melhorar a velocidade do NNS. Mas MySQL e PostgreSQL são os DBMS mais apropriados para mim.

database-design performance

4 respostas

  1. Best Answer

    PostgreSQL 9.6 usandocube

    Primeiro instale a extensão do cubo

    CREATE EXTENSION cube;

    Agora vamos criar um espaço n-dimensional com 100.000 pontos em 50 dimensões. Além disso, adicionaremos um índice 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;

    Agora vamos gerar um único ponto e usar o <->operador para encontrar o ponto mais próximo usando a distância Euclediana.

    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;

    O PostgreSQL 9.6+ suporta outros operadores de distância em cube. Todos podem usar o índice GIST que criamos. Nomeadamente,

    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.

    Dito isso, há uma ressalva,

    Para tornar mais difícil para as pessoas quebrarem as coisas, há um limite de 100 no número de dimensões dos cubos. Isso é definido em cubedata.h se você precisar de algo maior.

    Você pede 150 dimensões. Isso pode apresentar uma pequena complicação.

    • 19

  2. Considere realizar a redução de dimensão primeiro (por exemplo, Análise de Componentes Principais).

    Então você está fazendo NN em um pequeno número de dimensões com maior desempenho.

    Você pode usar Pl/R para executar o PCA dentro do postgres, se necessário.

    • 2

  3. Dê uma olhada em https://github.com/a-mma/AquilaDB é um banco de dados vetorial para armazenar Vetores de Recursos junto com Metadados JSON. Mantenha-o junto com seu RDBMS e use metadados para manter a referência cruzada entre os dados.

    • 1

  4. Dê uma olhada em FLANN e OpenCV .

    Infelizmente, não tenho conhecimento de uma integração disso em um sistema RDBMS. Mas há, por exemplo, integração de informações de estrutura química com o Posgres. Então, em princípio, isso pode ser feito.

    • 0

relate perguntas