Solución:
Probablemente usaría una versión modificada * de k-significa agrupar usando 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 vean. Además, puedes elegir k para adaptarse a sus requisitos de ancho de banda, y cada clúster 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 también pertenecía. Obviamente, querrá actualizar la agrupación en clústeres periódicamente si sus datos son dinámicos. No sé si podría hacer eso con un procedimiento almacenado y un disparador, pero tal vez.
* 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ía con un montón de puntos con altitud negativa (cuando se vuelva a convertir a LLH).
Si está agrupando en una ubicación geográfica, y no puedo imaginar que sea otra cosa :-), puede almacenar el “ID del 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 100×100 (10,000 grupos) y cada coordenada se asigna a uno de esos grupos.
Luego, puede detectar coordenadas muy cercanas seleccionando aquellas en el mismo cuadrado y moderadamente cercanas seleccionando aquellas en cuadrados adyacentes.
El tamaño de sus cuadrados (y, por lo tanto, el número de ellos) se decidirá según la precisión con la que necesite que sea la agrupación. Obviamente, si solo tiene una matriz de 2×2, podría obtener algunas agrupaciones de coordenadas que están muy separadas.
Siempre tendrá los casos de borde, como dos puntos juntos pero en diferentes grupos (uno más al norte en un grupo, el otro más al sur en otro) pero puede ajustar el tamaño del grupo O postprocesar los resultados en el lado del cliente.
Hice algo similar para una aplicación geográfica en la que quería asegurarme de poder almacenar en caché conjuntos de puntos fácilmente. Mi código de 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 a partir de ahí. Tenía un código para capturar todos los fragmentos de un punto dado a un radio dado que se traduciría en un solo multiget de Memcache (y algo de código para rellenar eso cuando faltaba).