¿La manera más eficiente de guardar puntos de paso y hacer comparaciones?

Question

Me gustaría conocer su opinión. Creé una aplicación, donde los usuarios crean rutas y rastreamos esta ruta y guardamos puntos de la base de datos. Luego, la aplicación hace comparaciones de los puntos de paso de los usuarios.

Actualmente, utilizo un servidor MSSQL, usando dos tablas, una para Rutas y la otra para almacenar puntos de ruta (con tipo de datos espaciales). Las comparaciones se realizan en un procedimiento almacenado utilizando las funciones geográficas de SQL Server, como st_distance ...

He investigado otras opciones. Uno que implementé es con Oracle 11g usando objetos. Guardo todos los datos en una sola Tabla de objetos y los puntos de ruta se almacenan en una variedad de un tipo con atributos de latitud y longitud. De esta manera es muy eficiente guardar y recuperar datos, pero se complica un poco al comparar.

Estoy buscando una solución NoSQL, algún algoritmo o método para hacerlo de manera eficiente. ¿Qué piensas?

Answer 1

El uso de funciones de base de datos como STDistance para todos los n registros es subóptimo. Su sobrecarga de la CPU aumentará exponencialmente.

Lo que debe hacer es verificar la cantidad de puntos dentro de un rectángulo alrededor del epicentro actual que está buscando. Aquí hay un ejemplo (en MySQL):

SELECT * FROM `points` 
    WHERE `latitude` >= X1 AND `latitude` <= X2 
    AND `longitude` >= Y1 AND `longitude` <= Y2 

Esto proporciona una reducida superset de puntos que entonces debe reducirse aún más mediante el cálculo de la distancia ortodrómica (con respecto a la curvatura de la Tierra), utilizando el Haversine formula.

No se olvide para establecer un composite index en latitude y longitude.

Aquí está en PHP:

<?php 
function haversine($latitude1, $longitude1, 
        $latitude2, $longitude2, $unit = 'Mi') { 
    $theta = $longitude1 - $longitude2; 
    $distance = (sin(deg2rad($latitude1)) * sin(deg2rad($latitude2))) + 
    (cos(deg2rad($latitude1)) * cos(deg2rad($latitude2)) * cos(deg2rad($theta))); 
    $distance = acos($distance); 
    $distance = rad2deg($distance); 
    $distance = $distance * 60 * 1.1515; 
    switch ($unit) { 
    case 'Mi': 
     break; 
    case 'Km': 
     $distance = $distance * 1.609344; 
    } 
    return (round($distance, 2)); 
} 
?> 

Para recapitular:

Aquí es una imagen de ejemplo que ilustra lo que debe hacer:

La primera búsqueda implicaría una búsqueda de colisión de cuadro delimitador (ejemplo de MySQL) para determinar el superset, excluyendo los puntos rojos. El segundo proceso de verificación implicaría calcular si los puntos están dentro de una distancia ortodrómica adecuada con la fórmula de Haversine (ejemplo de PHP) y tomando un subset (compuesto por los puntos negros).