Cálculo distribuído de distância geométrica entre vetores

5

Eu estou olhando para uma maneira de baixa latência em larga escala para calcular a distância geométrica entre os vetores.

Digamos que eu tenha um vetor A. Ele tem tamanho 128 e tipo 32 bit float. Eu quero obter sua distância geométrica de cerca de 10 milhões de outros vetores do mesmo tipo. Então, basicamente, até que ponto é A de todos os outros vetores. O resultado também deve ser retornado em uma ordem classificada. (Edit, o resultado deve retornar top N vector id's para o cliente)

Esta operação está vinculada à UX de um site e precisa ter baixa latência e será chamada pelo menos duas vezes por sessão do cliente.

Com vetores bidimensionais, o GeoIndexing pode ser usado. Mas eu não encontrei uma solução de indexação para dimensões mais altas.

Qual abordagem / tecnologia seria adequada para resolver esse problema?

    
por Henry Chinner 25.04.2016 / 14:27
fonte

1 resposta

1

Eu criei uma funcionalidade semelhante para um site. No meu caso, eu tinha menos dimensões do que você, mas eu tinha 15 milhões de registros (semelhante ao seu caso). Eu precisava atender cerca de 5000 solicitações por segundo, o que significa que cada solicitação tem um orçamento de cerca de 10 ms em um servidor de 64 núcleos.

Eu tentei várias abordagens, incluindo k-d tree e depois de benchmarking cada abordagem acabou com a descrita abaixo, que estava bem dentro do meu orçamento de 10ms quando escrita em c # e rodando em .net 4.0.

O algoritmo é mais fácil de desenhar que escrever, então espero que você possa seguir minha explicação. Vamos pensar nisso em 2 dimensões primeiro (é mais fácil visualizar) e depois estendê-lo para mais dimensões depois.

Imagine que você tenha um conjunto de 10 milhões de pontos com as coordenadas x e y em um espaço 2D. Faça um loop em todos os pontos e encontre os valores mínimo e máximo de x e y, e também o valor de x e y, onde metade dos pontos estão acima e metade dos pontos estão abaixo desse valor. Isso lhe dá um espaço retangular dividido em quatro quadrantes, onde cada quadrante contém o mesmo número de pontos.

Repita isso em cada um dos quatro quadrantes dividindo-os em quatro quadrantes e repita recursivamente até que os quadrantes contenham um número de pontos semelhante ao N em seu Top-N. Ao fazer isso, certifique-se de que cada ponto saiba qual retângulo está dentro e os retângulos conhecem a estrutura de aninhamento dos retângulos dentro dos retângulos.

Construir este índice leva um tempo, mas você só precisa reconstruí-lo completamente de vez em quando (talvez uma vez por dia). Ao longo do dia, à medida que os dados mudam, você pode mover pontos de um retângulo para outro. À medida que você move os pontos ao redor do índice, torna-se desequilibrado e menos eficiente, portanto, é necessário reconstruir a partir do zero de vez em quando.

Quando você quiser encontrar os N vizinhos mais próximos, você só precisa considerar os retângulos adjacentes. Digamos que você esteja procurando pelos 10 vizinhos mais próximos, então o índice continuará dividindo os retângulos em 4 quadrantes até que cada retângulo contenha aproximadamente 10 pontos. Agora os 10 pontos mais próximos devem estar no mesmo retângulo ou em um dos retângulos adjacentes. Você pode encontrar os retângulos adjacentes indo até a árvore retangular e descendo até as crianças. Se você estiver em um limite, talvez tenha que subir alguns níveis e voltar ao mesmo número de níveis, mas pode pré-computar a lista de retângulos adjacentes para cada retângulo para torná-lo mais rápido (mas use mais memória). Note que a maioria dos retângulos está no meio em algum lugar e terá 8 retângulos adjacentes. Retângulos na borda do espaço de coordenadas terão menos.

Para estender isso de 2D para 3D, o espaço inteiro é agora um cubo em vez de um retângulo e você divide cada cubo em 8 cubos menores, cada um contendo o mesmo número de pontos, em vez de dividir retângulos em quatro retângulos menores e cada cubo terá até 26 cubos adjacentes.

Isso pode ser estendido logicamente para mais dimensões. Na minha aplicação eu tinha 4 (latitude, longitude e 2 outros). No seu caso, os números ficam muito grandes, então você vai precisar de muita memória! Eu não fiz as contas, mas dividir cada região de 128 dimensões ao meio em cada dimensão pode resultar em 2 ^ 128 regiões filho - o que claramente não é viável. Se este for o caso, acho que você precisará experimentar variações dessa abordagem, mas esperamos que isso lhe dê um ponto de partida.

Observe que esse algoritmo é imperfeito por design. As imperfeições não importavam para meu aplicativo e a velocidade era muito mais importante. A imperfeição vem do fato de que os retângulos são subdivididos por número de pontos e não por tamanho, portanto os retângulos adjacentes não estão alinhados com esse retângulo. Isso não importa muito, porque você ainda deve calcular a distância real do ponto alvo para todos os seus retângulos vizinhos e pegar o N mais próximo, e você também sabe que, mesmo que o retângulo adjacente não esteja exatamente alinhado com este, não há outros retângulos que estão mais próximos.

    
por 12.08.2016 / 22:26
fonte