Início / dba / Perguntas / 158653
Accepted
konstantin_doncov
Asked: 2016-12-20 19:56:22 +0800 CST

Pesquise rapidamente os objetos mais semelhantes no espaço n-dimensional

  • 772

Vamos supor que temos a pontos no espaço n-dimensional. Portanto, temos um coords (n colunas) que pode descrever a localização de cada ponto.

Precisamos implementar uma tabela que possa ser utilizada para uma busca rápida dos pontos mais semelhantes, ou seja, pontos que tenham a menor distância até o ponto desejado.

Ex.: pontos no db:

id  c1  c2  c3  c4  c5
1   5   19  42  12  16
2   3   23  38  15  12
3   14  21  32  33  1
4   12  29  21  24  5

Se quisermos encontrar a melhor correspondência para pontos com coordenadas:

c1 c2  c3  c4  c5
4  20  40  14  15

Obteremos pontos com id 1 e 2.

Também temos coordenada média para cada dimensão (coluna) e vetor para cada ponto em que primeiro elemento - número da dimensão em que o ponto tem a maior diferença da coordenada média nessa dimensão e último - número da dimensão em que ponto tem a menor diferença. Talvez possa ser usado para os pontos de filtragem mais rápidos que possuem a maior distância até o ponto desejado.

Então, como posso fazer algo assim usando o MySQL?

Acho que o índice composto order by abs(cx - $mycx)pode ser uma boa solução, mas não posso usá-lo porque terei mais de 16 colunas que preciso incluir em um índice.

Qualquer ajuda será muito útil!

mysql database-design

2 respostas

  1. Best Answer

    PostgreSQL usandocube

    Usando o PostgreSQL, isso se torna muito fácil com a cubeextensão que expliquei em sua outra pergunta . Dados de amostra.

    CREATE TABLE foo AS
SELECT *
FROM ( VALUES
  (1, cube(ARRAY[5 , 19, 42, 12, 16]) ),
  (2, cube(ARRAY[3 , 23, 38, 15, 12]) ),
  (3, cube(ARRAY[14, 21, 32, 33, 1 ]) ),
  (4, cube(ARRAY[12, 29, 21, 24, 5 ]) )
) AS t(id, c);

    Encontrar distância...

    SELECT
  id,
  c,
  c2,
  cube_distance(c,c2),
  rank() OVER (ORDER BY cube_distance(c,c2))
FROM foo
CROSS JOIN ( SELECT cube(ARRAY[4,20,40,14,15]) )
  AS t(c2)
ORDER BY cube_distance(c, c2);

    Saídas.

     id |          c          |         c2          |  cube_distance   | rank 
----+---------------------+---------------------+------------------+------
  1 | (5, 19, 42, 12, 16) | (4, 20, 40, 14, 15) |  3.3166247903554 |    1
  2 | (3, 23, 38, 15, 12) | (4, 20, 40, 14, 15) | 4.89897948556636 |    2
  4 | (12, 29, 21, 24, 5) | (4, 20, 40, 14, 15) | 26.5706605111728 |    3
  3 | (14, 21, 32, 33, 1) | (4, 20, 40, 14, 15) | 26.8700576850888 |    4
    • 3

  2. Plano A: (Na ausência de mais informações, prefiro esta solução.)

    ORDER BY 
    ABS(c1 - $c1) +
    ABS(c2 - $c2) +
    ABS(c3 - $c3) +
    ABS(c4 - $c4) +
    ABS(c5 - $c5)  ASC

    Ou "raiz quadrada média" (sem o SQRT desnecessário):

    ORDER BY 
    (c1 - $c1) * (c1 - $c1) +
    (c2 - $c2) * (c2 - $c2) +
    ...  ASC

    Para encontrar o item 'mais próximo' de uma única consulta ($c1, $c2, ...), isso requer uma única passagem pelos dados. Se os dados forem grandes, eles serão limitados por E/S, de modo que a velocidade do disco se torna a restrição dominante. Os quadrados serão apenas ligeiramente mais lentos do que ABS(), então escolha a métrica de sua preferência. (Observação: o uso POW(, 2)pode ser perceptível mais lento.)

    Nenhum índice é útil nesta consulta.

    Você pode adicionar LIMIT 10para obter os 10 "mais próximos". Se você quiser encontrar todos aqueles com exatamente a mesma métrica (e mais próximos), o código se tornará muito mais confuso e lento.

    Plano B: Se os números "funcionarem corretamente", pode ser possível usar um índice em uma coluna. Ao fazer isso, você primeiro localizaria as linhas "próximas" do valor dessa coluna. (Essa lista não deve exceder 10% da tabela.) Em seguida, use o código acima para passar laboriosamente por esse subconjunto de linhas. O risco é que as outras colunas podem estar muito próximas, enquanto esta coluna está muito longe para ser filtrada na primeira passagem.

    O plano C é útil para encontrar as pizzarias mais próximas , mas não se estende além de 2 dimensões.

    • 1

relate perguntas