Cálculo de vizinho mais próximo repetido para milhões de pontos de dados muito lentos

Eu tenho um conjunto de dados rodando em milhões de pontos de dados em 3D. Para o cálculo que estou fazendo, preciso calcular vizinho (pesquisa por faixa) para cada ponto de dados em um raio, tentar ajustar uma função, calcular o erro para o ajuste, repetir para o próximo ponto de dados e assim por diante. Meu código funciona corretamente, mas está demorando muito tempo para ser executado, cerca de 1 segundo por ponto de dados! Provavelmente porque, para cada ponto, ele deve procurar no conjunto de dados inteiro. Existe uma maneira de acelerar o processo. Eu tenho uma ideia de que, se eu puder estabelecer alguma relação de adjacência entre os primeiros vizinhos, isso poderá ser menos lento. Se ajudar, estou tentando encontrar a largura ideal da janela Parzen em 3D.

Eu sugeriria pesquisar no Google para hierarquias delimitadoras de volume (árvore BSP em particular). Dada a sua nuvem de pontos, você pode encontrar um plano que a divide em duas sub-nuvens iguais. Então, quando você precisar encontrar a coleção de pontos que estão dentro do raio R de um ponto de teste, você pode primeiro comparar seu ponto de teste com o plano e, se a altura acima dele for maior que R, toda a subcloud abaixo do plano também deve estar mais distante do que R (para que você não precise verificar nenhum desses pontos). Você também pode aplicar essa ideia recursivamente, resultando em complexidades do tipo n log n em vez de n-quadrado. (Esse é o particionamento de espaço binário / BSP,

Existem várias estruturas de dados para armazenar dados que preservam informações sobre posição e proximidade; permitindo a rápida determinação do (s) vizinho (s) mais próximo (s).

Em particular , árvores R (e formas especializadas como árvores R * ) e árvores X . Muitas opções otimizadas para usos ligeiramente diferentes.

Escolher uma árvore R * em vez de uma pesquisa ingênua do vizinho mais próximo foi uma grande parte da minha obtenção de um fator de 10000 acelerações de um código específico. (OK, talvez algumas centenas delas fossem a árvore R *, a maior parte do resto foi porque a pesquisa ingênua havia sido mal codificada para quebrar o cache. :: sigh :: )

Essas estruturas possuem desempenho típico de inserção de ( N o número de pontos armazenados) e requisitos de armazenamento e desempenho de pesquisa de O ( log N ) ; portanto, elas funcionam bem se você realizar muitas pesquisas (por exemplo, uma para cada ponto como em DBSCAN); no entanto, alguns deles têm um desempenho de pior caso muito ruim.$O(N \log N)$$N$$O(\log N)$

Isso é muito semelhante a um dos maiores desafios no campo da dinâmica molecular - computando todas as interações aos pares entre partículas não ligadas.

Lá, usamos listas de células (ou listas de vizinhos ) para nos ajudar a descobrir o que está próximo; para esta aplicação, a lista de células é provavelmente o algoritmo mais fácil de usar:

• Divida a caixa em uma série de células.
• Para cada partícula, determine a qual célula deve ser atribuída (O (1) por partícula).
• Então, para cada partícula, verifique a célula "própria" mais as células vizinhas; se algum deles estiver ocupado, nenhuma pesquisa adicional será necessária.
• Se todos os vizinhos mais próximos estiverem vazios, expanda para os vizinhos mais próximos e assim por diante, até encontrar uma partícula.

Se o seu sistema tiver uma distribuição mais ou menos uniforme de partículas, isso reduzirá bastante o custo do seu algoritmo, de acordo com a aspereza da grade. No entanto, é necessário algum ajuste fino: uma grade muito grossa e você não economizará muito tempo; muito bom e você passará muito tempo pedalando por células vazias da grade!

Você definitivamente deve verificar as árvores e os arredores de KD que são os métodos de escolha para os conjuntos de pontos (enquanto os BSPs são para objetos gerais e as grades para densidades mais ou menos uniformes). Eles podem ser muito compactos e rápidos, minimizando a sobrecarga na memória e na computação e são simples de implementar.

Quando seus pontos são distribuídos de maneira mais ou menos uniforme (mesmo com áreas vazias, mas não deve haver singularidade de densidade ou outra alta concentração), verifique os pacotes de esferas se quiser tentar uma subdivisão de espaço não hierárquico semelhante a uma grade.

Você provavelmente deve considerar a construção da triangulação de Delaunay (bem, seu análogo 3D). Em 2D, é uma triangulação especial dos pontos de dados que sempre contém o vizinho mais próximo. O mesmo acontece em 3D, mas com tetraedros.

$n \log(n)$

Espero que ajude!