database - Agrupación de Lat/Longs en una base de datos
latitude-longitude cluster-analysis (6)
Estoy tratando de ver si alguien sabe cómo agrupar algunos resultados Lat / Long, usando una base de datos, para reducir el número de resultados enviados a través de la conexión a la aplicación.
Hay una serie de recursos sobre cómo agrupar, 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 :(
Esta es una pregunta similar , hecha por un compañero SO miembro. Las soluciones están basadas en el lado del servidor (es decir, detrás del código C #).
¿Alguien ha tenido suerte o experiencia para resolver esto, pero en una base de datos? ¿Hay algún gurú de la base de datos que esté detrás de un desafiante y sexy DB desafío?
por favor ayuda :)
EDIT 1: Aclaración: al agrupar, espero agrupar x 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.
Creo que puedes usar los tipos de datos espaciales de MSSQL . 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.
Hice algo similar para una aplicación geográfica en la que quería asegurarme de que podía almacenar en caché conjuntos de puntos fácilmente. Mi código geohashing 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 puso realmente fácil desde allí. 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).
Para movielandmarks.com usé el código de clúster de Mike Purvis , uno de los autores de Beginning Google Maps Applications con PHP y 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.
Probablemente usaría una versión modificada * de k- means clustering usando las coordenadas cartesianas (por ejemplo, WGS-84 ECF) para sus puntos. Es fácil de implementar y converge rápidamente, y se adapta a sus datos sin importar cómo se vean. Además, puede elegir k para satisfacer sus requisitos de ancho de banda, y cada grupo tendrá la misma cantidad 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é grupo pertenecía también. Obviamente, desea actualizar el clúster periódicamente si sus datos son dinámicos. No sé si podrías hacer eso con un procedimiento almacenado y 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).
Si se está agrupando en una ubicación geográfica, y no puedo imaginar que sea otra cosa :-), podría almacenar la "ID del clúster" 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 coordenada se asigna a uno de esos grupos.
Luego, puede detectar coordenadas muy cercanas seleccionando aquellas en el mismo cuadrado y cerrándose moderadamente al seleccionarlas en cuadrados adyacentes.
El tamaño de tus cuadrados (y, por lo tanto, el número de ellos) se decidirá por la precisión con la que necesites el clúster. Obviamente, si solo tienes una matriz de 2x2, podrías obtener un conjunto de coordenadas que están muy lejos.
Siempre tendrá los casos de borde, como dos puntos juntos, pero en diferentes grupos (uno más al norte en su grupo, el otro más al sur) pero puede ajustar el tamaño del grupo o procesar los resultados en el lado del cliente.