Google Maps y Uber son sólo algunos ejemplos de las aplicaciones más populares que trabajan con datos geográficos. Almacenar información sobre millones de lugares en el mundo les obliga a almacenar y operar de manera eficiente posiciones geográficas, incluido el cálculo de distancias y la búsqueda de los vecinos más cercanos.
Todas las aplicaciones geográficas modernas utilizan ubicaciones 2D de objetos representados por longitud y latitud. Si bien puede parecer ingenuo almacenar los geodatos en forma de pares de coordenadas, este enfoque presenta algunos inconvenientes.
En este artículo, discutiremos los problemas subyacentes del enfoque ingenuo y hablaremos sobre otro formato moderno utilizado para acelerar la manipulación de datos en sistemas grandes.
Nota. En este artículo, representaremos el mundo como un gran rectángulo 2D plano en lugar de una elipse 3D. La longitud y la latitud estarán representadas por las coordenadas X e Y respectivamente. Esta simplificación facilitará el proceso de explicación sin omitir los detalles principales.
Imaginemos una base de datos que almacena coordenadas 2D de todos los objetos de la aplicación. Un usuario inicia sesión en la aplicación y quiere encontrar los restaurantes más cercanos.
Si las coordenadas simplemente se almacenan en la base de datos, entonces la única forma de responder a este tipo de consulta es iterar linealmente a través de todos los objetos posibles y filtrar los más cercanos. Obviamente, este no es un enfoque escalable y la búsqueda sería extremadamente lenta en la aplicación real.
Las bases de datos SQL permiten la creación de una índice — una estructura de datos construida sobre una determinada columna de una tabla que acelera el proceso de búsqueda por claves en esa columna.
Otro enfoque incluye crear un índice en una de las columnas de coordenadas. Cuando un usuario realiza una consulta, la base de datos puede en O(1) tiempo recuperar la posición de la fila en la tabla correspondiente a la posición actual del usuario.
Gracias al índice construido, la base de datos también puede encontrar rápidamente las filas con el valor de coordenadas más cercano. Luego es posible tomar un conjunto de dichas filas y luego filtrar aquellas cuya distancia euclidiana total desde la posición del usuario sea menor que un cierto radio de búsqueda.
Si bien el enfoque descrito es mejor que el anterior, requiere tiempo para filtrar las filas con las distancias más cercanas. Además, puede haber casos en los que las filas inicialmente seleccionadas con las coordenadas más cercanas no sean en realidad las más cercanas a la posición del usuario.
Una sola tabla no puede tener dos índices simultáneamente. Es por eso que para resolver este problema, ambas coordenadas deben representarse como un único valor combinado conservando la información sobre las distancias. Este objetivo se logra exactamente mediante los quadtrees que se analizan en la siguiente sección.
A árbol cuádruple es una estructura de datos de árbol utilizada para la partición recursiva de un espacio 2D en cuatro cuadrantes. Dependiendo de la estructura del árbol, cada nodo padre puede tener de 0 a 4 hijos.
Como se muestra en la imagen de arriba, cada cuadrado en un nivel actual se divide por cuatro subcuadrados iguales en el siguiente nivel. Como resultado, codificar un solo cuadrado en el nivel i requiere 2 * yo bits.
Si un mapa geográfico se divide de esta manera, podemos codificar todas sus subpartes con una cantidad personalizada de bits. Cuantos más niveles se utilicen en el quadtree, mejor será la precisión.
Propiedades
Los Quadtrees se utilizan particularmente en aplicaciones geográficas por varias ventajas:
- Debido a su estructura, los quadtrees permiten un rápido recorrido por los árboles.
- Cuanto mayor sea el prefijo común de dos cadenas utilizadas para codificar un par de puntos en el mapa, más cerca estarán. Sin embargo, esto no ocurre al revés en el caso extremo: un par de puntos pueden estar muy cerca uno del otro pero tener un pequeño prefijo común. Aunque ocurren casos extremos, no son tan frecuentes: solo ocurren cuando dos cuadrantes pequeños están ubicados en lados opuestos de un borde con otro cuadrante mucho más grande.
- Si un cuadrante está representado por una cadena s₁s₂…sᵢ, entonces todos los subcuadrantes que contiene están representados por cadenas x como s₁s₂…sᵢ < x < s₁s₂…sⱼ, donde sⱼ es el siguiente carácter después de sᵢ en el orden lexicográfico.
Ventajas
La principal ventaja de los quadtrees es que cada posición en un mapa está representada por un identificador de cadena único que se puede almacenar en una base de datos como una sola columna, lo que permite para construir un índice en cadenas quadtree. Por lo tanto, dada cualquier cadena que represente una región en el mapa, se vuelve muy rápida:
- subir a niveles superiores o pasar a niveles inferiores de la región;
- acceder a todas las subregiones de la región;
- para encontrar hasta las 8 regiones adyacentes en el mismo nivel (excepto en los casos extremos).
En la mayoría de las aplicaciones geográficas reales, se utiliza el formato GeoHash, que es una ligera modificación del formato quadtree:
- en lugar de cuadrados, las regiones geográficas se dividen mediante rectángulos;
- las regiones se dividen en más de cuatro partes;
- Cada objeto en el mapa está codificado por una cadena en el formato “base 32”formato que consta de dígitos del 0 al 9 y letras minúsculas, excepto “a”, “i”, “l” y “o”.
A pesar de estas ligeras modificaciones, GeoHash conserva las importantes ventajas que se describieron en la sección anterior para quadtrees.
La siguiente tabla muestra la correspondencia entre cada nivel de GeoHash y los tamaños de rectángulo. En la gran mayoría de los casos, los niveles 9 y 10 ya son suficientes para dar una aproximación muy precisa sobre el mapa.
Encontrar los objetos más cercanos en el mapa.
Si tenemos un objeto en el mapa, podemos encontrar sus objetos más cercanos dentro de una cierta distancia d usando el siguiente algoritmo:
- Convirtiendo el objeto a la cadena GeoHash s.
2. Encontrar el primer nivel GeoHash más pequeño i cuyo tamaño sea mayor que la distancia requerida d.
3. Tome los primeros i caracteres de la cadena s (para representar el rectángulo que contiene el objeto inicial en el nivel k).
4. Encuentra 8 regiones adyacentes alrededor de la cuerda s.[0 … i – 1].
5. Encuentre todos los objetos en las regiones inicial y adyacente y filtre aquellos objetos cuya distancia al objeto inicial sea menor que d.
La navegación rápida es un aspecto crucial de las geoaplicaciones que utilizan datos sobre millones de usuarios y lugares. El método clave para lograrlo incluye la creación de un identificador de índice único que pueda representar implícitamente tanto la latitud como la longitud.
Al heredar las propiedades más importantes de los quadtrees, el servidor GeoHash es un gran ejemplo de un método que realmente logra un gran rendimiento en la práctica. El único lado débil es la presencia de casos extremos cuando ambos objetos están ubicados en lados diferentes de un gran borde que los separa. Aunque pueden afectar negativamente la eficiencia de la búsqueda, los casos extremos no aparecen con tanta frecuencia en la práctica, lo que significa que GeoHash sigue siendo la mejor opción para las geoaplicaciones.
En caso de que esté familiarizado con el aprendizaje automático y desee obtener más información sobre formas optimizadas de realizar tareas escalables. búsqueda de similitud sobre incrustaciones, te recomiendo que pases por mis otros serie de artículos en eso:
Búsqueda de similitud
Todas las imágenes, a menos que se indique lo contrario, son del autor.