konstantin_doncov's questions

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.

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!