Atualmente, estou enfrentando o problema de encontrar uma maneira de agrupar em torno de 500.000 pares de latitude / longitude em python. Até agora, tentei computar uma matriz de distância com numpy (para passar para o DBSCAN do scikit-learn), mas com uma entrada tão grande, ela rapidamente gera um erro de memória.

Os pontos são armazenados em tuplas contendo a latitude, longitude e o valor dos dados nesse ponto.

Em resumo, qual é a maneira mais eficiente de agrupar espacialmente um grande número de pares de latitude / longitude em python? Para esta aplicação, estou disposto a sacrificar alguma precisão em nome da velocidade.

Edit: O número de clusters para o algoritmo encontrar é desconhecido antes do tempo.