Clustering Lat / Longs em um banco de dados

Question

Eu estou tentando ver se alguém sabe como se agrupar alguns resultados Lat / Long, utilizando um banco de dados, para reduzir o número de resultados enviado através do fio para a aplicação.

Há uma série de recursos sobre como cluster, tanto no lado do cliente ou no lado do servidor (aplicação) .. mas não no lado do banco de dados: (

Esta é uma pergunta semelhante, perguntado por um colega S. O. membro. As soluções são baseadas lado do servidor (ie. C por trás # código).

Alguém já teve alguma sorte ou experiência com a solução deste, mas em um banco de dados? Há algum guru de banco de dados está lá fora que estão atrás de um desafio hawt e DB sexy?

Por favor, ajude:)

EDIT 1: Esclarecimento - por clustering, eu estou esperando para número x grupo de pontos em um único ponto, para uma área. Então, se eu digo tudo aglomerado em uma 1 milha / 1 km quadrados, em seguida, todos os resultados em que 'quadrado' são GROUP'D em um único resultado (digamos ... no meio da praça).

EDIT 2:. Estou usando o MS SQL 2008, mas estou aberto para ouvir se há outras soluções em outro DB

Answer 1

Eu provavelmente usar uma versão modificada do * k -means agrupamento usando o cartesiano (por exemplo WGS-84 ECF) coordenadas para os seus pontos. É fácil de implementar e converge rapidamente, e se adapta a seus dados, não importa o que parece. Além disso, você pode escolher k para atender às suas necessidades de largura de banda, e cada grupo terá o mesmo número de pontos associados (mod k).

Eu faria uma tabela de centróides cluster e adicionar um campo para a mesa de dados original para indicar o que agrupam pertencia também. Você teria, obviamente, deseja atualizar o agrupamento periodicamente se os seus dados é de todo dinâmico. Eu não sei se você pode fazer isso com um procedimento e gatilho armazenado, mas talvez.

* A "modificação" seria para ajustar o comprimento dos vetores centroid computados para que eles estaria na superfície da terra. Caso contrário, você pode acabar com um monte de pontos com altitude negativo (quando volta convertido para LLH).

Answer 2

Se você é o agrupamento da localização geográfica, e eu não posso imaginar que seja outra coisa :-), você pode armazenar o "ID do cluster" no banco de dados juntamente com as coordenadas latitude / longitude.

O que quero dizer com isso é dividir o mapa do mundo em (por exemplo) uma matriz de 100x100 (10.000 clusters) e cada co-ordenada é atribuído a um desses clusters.

Em seguida, você pode detectar coordenadas muito próximos, selecionando aqueles na mesma praça e aqueles moderadamente próximos, selecionando aqueles em quadrados adjacentes.

O tamanho de seus quadrados (e, portanto, o número deles) será decidida por quão preciso é necessário o agrupamento ser. Obviamente, se você só tem uma matriz 2x2, você poderia obter algum agrupamento de coordenadas que são um longo caminho de distância.

Yo terá sempre os casos de ponta, tais como dois pontos juntos, mas em diferentes clusters (um mais setentrional em seu conjunto, o outro mais ao sul em seu), mas você pode ajustar o tamanho do cluster ou pós- processar os resultados no lado do cliente.

Answer 3

Eu fiz uma coisa semelhante para uma aplicação geográfica onde eu queria para garantir que eu poderia armazenar em cache conjuntos de pontos facilmente. Meus geohashing olhares código como este:

def compute_chunk(latitude, longitude)
  (floor_lon(longitude) * 0x1000) | floor_lat(latitude)
end

def floor_lon(longitude)
  ((longitude + 180) * 10).to_i
end

def floor_lat(latitude)
  ((latitude + 90) * 10).to_i
end

Tudo ficou muito fácil de lá. Eu tinha algum código para pegar todos os pedaços de um determinado ponto de um determinado raio que se traduziria em um único Multiget memcache (e algum código para aterro que, quando se estava faltando).

Answer 4

Para movielandmarks.com eu usei o código de agrupamento de Mike Purvis , um dos autores de A partir do Google Maps Aplicações com PHP e AJAX . Ele constrói árvores de clusters / pontos para diferentes níveis de zoom usando PHP e MySQL, armazená-lo no banco de dados de modo que a recordação é muito rápido. Algumas delas podem ser úteis para você mesmo se você estiver usando um banco de dados diferente.

Answer 5

Por que não testar várias abordagens?

1. traduzir o href="http://www.cs.waikato.ac.nz/ml/weka/" rel="nofollow noreferrer"> weka biblioteca em .NET CLI com IKVM.NET
2. adicionar uma assembleia resultou do seu código e weka.dll (uso ilmerge) em seu banco de dados

Faça alguns testes, o que é. No agrupamento específico funciona melhor do que qualquer outra pessoa.

Answer 6

Eu acredito que você pode usar tipos de dados espaciais de MSSQL . Se eles são semelhantes a outros tipos de dados espaciais que conheço, eles vão guardar seus pontos em uma árvore de retângulos, e então você pode ir para os retângulos de baixa resolução para obter aglomerados implícitas.