Clustering Lat/Longs en una base de datos

Question

Estoy tratando de ver si alguien sabe cómo agrupar algunos resultados de Lat/Long, usando una base de datos, para reducir la cantidad de resultados enviados a la aplicación a través del cable.

Hay una serie de recursos sobre la forma de agruparse, ya sea en el lado del cliente o en el lado del servidor (aplicación) .. pero no en el lado de la base de datos :(

This is a similar question, se le preguntó por un compañero miembro de SO Las soluciones están basadas en el servidor (es decir, código C# detrás).

¿Alguien ha tenido algo de suerte o experiencia al resolver esto, pero en una base de datos? ¿Hay algún gurú de base de datos que esté detrás de un hawt y sexy DB? desafío?

por favor ayuda :)

EDIT 1: Aclaración: al agrupar, espero agrupar x número de puntos en un solo punto, para un área. Entonces, si digo agrupar todo en un cuadrado de 1 milla/1 km, entonces todos los resultados en ese 'cuadrado' son GROUP'D en un solo resultado (digamos ... el centro del cuadrado).

EDIT 2: Estoy usando MS Sql 2008, pero estoy abierto a escuchar si hay otras soluciones en otros DB.

Answer 1

Probablemente usaría una versión modificada * de k-means clustering utilizando las coordenadas cartesianas (por ejemplo, WGS-84 ECF) para sus puntos. Es fácil de implementar & converge rápidamente, y se adapta a sus datos sin importar cómo se vea. Además, puede elegir k para satisfacer sus requisitos de ancho de banda, y cada grupo tendrá el mismo número de puntos asociados (mod k).

Haría una tabla de centroides de clúster y agregaría un campo a la tabla de datos original para indicar a qué clúster pertenecía también. Obviamente, desea actualizar el clúster periódicamente si sus datos son dinámicos. No sé si podría hacer eso con un procedimiento almacenado & disparador, pero quizás.

* La "modificación" sería ajustar la longitud de los vectores centroides calculados para que estén en la superficie de la tierra. De lo contrario, terminarías con un montón de puntos con altitud negativa (cuando se vuelvan a convertir en LLH).

Answer 2

Si se está agrupando en una ubicación geográfica, y no puedo imaginar que sea otra cosa :-), podría almacenar la "ID de grupo" en la base de datos junto con las coordenadas lat/long.

Lo que quiero decir con eso es dividir el mapa mundial en (por ejemplo) una matriz de 100x100 (10,000 clústeres) y cada una de las coordenadas se asigna a uno de esos clústeres.

Luego, puede detectar coordenadas muy cercanas seleccionando aquellas en el mismo cuadrado y cerrándose moderadamente al seleccionarlas en casillas adyacentes.

El tamaño de sus cuadrados (y, por lo tanto, el número de ellos) se decidirá por la precisión con la que necesite el clúster. Obviamente, si solo tienes una matriz de 2x2, podrías obtener un conjunto de coordenadas que están muy lejos.

Yo siempre tendrá los casos extremos, tales como dos puntos cercanos juntos, pero en diferentes grupos (uno más al norte de su grupo, el otro meridional de su), pero se podía ajustar el tamaño del clúster O post-proceso de los resultados en el lado del cliente.

Answer 3

Hice algo similar para una aplicación geográfica en la que quería asegurarme de poder guardar en caché los conjuntos de puntos fácilmente. Mi código de geoanálisis se ve así:

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 

Todo se volvió realmente fácil a partir de ahí. Tenía un código para capturar todos los fragmentos desde un punto dado hasta un radio dado que se traduciría en un solo Memcache multiget (y algún código para rellenarlo cuando faltaba).

Answer 4

Para movielandmarks.com Utilicé el código de clúster de Mike Purvis, uno de los autores de Beginning Google Maps Applications with PHP and AJAX. Construye árboles de clústeres/puntos para diferentes niveles de zoom usando PHP y MySQL, almacenándolos en la base de datos para que la recuperación sea muy rápida. Parte de esto puede serle útil incluso si está usando una base de datos diferente.

Answer 5

Creo que puede usar MSSQL's spatial data types. Si son similares a otros tipos de datos espaciales que conozco, almacenarán sus puntos en un árbol de rectángulos, y luego podrán ir a los rectángulos de resolución más baja para obtener clústeres implícitos.

Answer 6

¿Por qué no probar varios enfoques?

1. traducen en la biblioteca weka .NET CLI con IKVM.NET
2. añadir una asamblea el resultado de su código y weka.dll (uso ILMerge) en su base de datos

hacer algunas pruebas, es decir. Ningún clúster específico funciona mejor que nadie.