Ingeniería de datos geoespaciales Indexación espacial
Geospatial Data Engineering Spatial Indexing
Optimizando consultas, mejorando tiempos de ejecución y aplicaciones de ciencia de datos geoespaciales
Introducción: ¿por qué es útil un índice espacial?
Al realizar trabajos de ciencia de datos geoespaciales, es muy importante pensar en optimizar el código que estás escribiendo. ¿Cómo puedes hacer que los conjuntos de datos con cientos de millones de filas se agreguen o se unan más rápido? Aquí es donde entran en juego conceptos como los índices espaciales. En esta publicación, hablaré sobre cómo se implementa un índice espacial, cuáles son sus beneficios y limitaciones, y echaré un vistazo a la biblioteca de índices H3 de código abierto de Uber para algunas aplicaciones interesantes de ciencia de datos espaciales. ¡Empecemos!
🗺 ¿Qué es un índice espacial?
Un índice regular es algo que podrías encontrar al final de un libro: una lista de palabras y dónde han aparecido en el texto. Esto te ayuda a buscar rápidamente cualquier referencia a una palabra que te interese dentro de un determinado texto. Sin esta herramienta útil, tendrías que buscar manualmente en cada página de tu libro, buscando esa única mención que quieres leer.
En las bases de datos modernas, esta cuestión de las consultas y búsquedas también es muy pertinente. La indexación a menudo hace que la búsqueda de datos sea más rápida que el filtrado, y puedes crear índices basados en una columna de interés. Para datos geoespaciales en particular, los ingenieros a menudo necesitan realizar operaciones como “intersección” o “está cerca de”. ¿Cómo podemos crear un índice espacial para que estas operaciones sean lo más rápidas posible? Primero, echemos un vistazo a algunos de estos datos geoespaciales:
Supongamos que queremos ejecutar una consulta para determinar si estas dos formas se están intersectando. Por construcción, las bases de datos espaciales crean su índice a partir de una caja delimitadora que contiene la geometría:
Para responder si estas dos características se intersectan, la base de datos comparará si las dos cajas delimitadoras tienen alguna área en común. Como puedes ver, esto puede llevar rápidamente a falsos positivos. Para solucionar este problema, las bases de datos espaciales como PostGIS suelen dividir estas grandes cajas delimitadoras en cajas más pequeñas y más pequeñas:
- Google marca con marcas de agua las imágenes generadas por intelige...
- Esta investigación de IA aborda el problema de la pérdida de plasti...
- Principales software/herramientas de traducción de IA (septiembre d...
Estas particiones se almacenan en R-trees. Los R-trees son una estructura de datos jerárquica: realizan un seguimiento de la “caja delimitadora” principal grande, sus hijos, los hijos de sus hijos y así sucesivamente. La caja delimitadora de cada padre contiene las cajas delimitadoras de sus hijos:
La operación “intersección” es una de las operaciones clave que se beneficia de esta estructura. Al realizar una consulta de intersección, la base de datos recorre este árbol preguntando: “¿la caja delimitadora actual se intersecta con la característica de interés?”. Si es así, mira las cajas delimitadoras de ese padre y hace la misma pregunta. A medida que lo hace, puede recorrer rápidamente el árbol, omitiendo las ramas que no tienen intersección y, por lo tanto, mejorar el rendimiento de la consulta. Al final, devuelve la geometría de intersección como se desea.
🧰 En la práctica: probando un índice espacial con GeoPandas
Ahora veamos en concreto cómo se ve usar un procedimiento de fila por fila vs un índice espacial. Utilizaré 2 conjuntos de datos que representan las áreas censales de la ciudad de Nueva York, así como las instalaciones de la ciudad (ambos licenciados a través de Open Data y disponibles aquí y aquí). Primero, probemos la operación de “intersección” en GeoPandas en una de las geometrías de las áreas censales. ‘Intersección’ en GeoPandas es una función de fila por fila que verifica cada fila de la columna de interés con nuestra geometría y determina si se intersectan o no.
GeoPandas también ofrece una operación de índice espacial que utiliza R-trees y nos permite realizar intersecciones también. Aquí hay una comparación de tiempo de ejecución de los dos métodos en 100 ejecuciones de la operación de intersección (nota: como la función de intersección predeterminada es lenta, solo seleccioné alrededor de 100 geometrías del conjunto de datos original):
Como puedes ver, el enfoque del índice espacial ofreció un rendimiento mucho mejor que el método de intersección convencional. De hecho, aquí están los intervalos de confianza del 95% para los tiempos de ejecución de cada uno:
¡Genial! Entonces, ¿por qué nunca no querríamos usar un índice espacial? ¿Existen casos en los que no ofrece beneficios? Bueno, sí. Algunas de estas limitaciones se deben a la forma en que el índice espacial almacena las hojas en los datos. Resulta que la forma en que se distribuyen los datos afecta cómo se colocan las cajas delimitadoras en el R-tree. Específicamente, si una gran cantidad de datos se concentra en el mismo espacio geográfico, tenderán a compartir los mismos padres y, por lo tanto, estarán agrupados juntos en las mismas ramas. Esto puede llevar a árboles sesgados que no ofrecen mucha optimización al realizar consultas.
💻 ¿Cómo se ven otros índices espaciales?
Otras compañías también han adaptado sus propios índices espaciales. Uber utiliza H3, un sistema de indexación jerárquica hexagonal que divide el mundo en hexágonos de área igual. Los hexágonos tienen muchos beneficios cuando se modela el movimiento de las personas alrededor de una ciudad o para problemas como calcular un radio. Los datos geoespaciales se agrupan en estos hexágonos, que sirven como la principal unidad de análisis de la compañía. La cuadrícula se construye superponiendo 122 celdas hexagonales en una proyección de mapa icosaédrico, y admite una amplia gama de funciones, incluidas agregaciones, uniones y aplicaciones de aprendizaje automático.
Este sistema, así como gran parte de su funcionalidad, es de código abierto y está disponible en GitHub para su análisis. Una de las funciones de la API de H3 es convertir puntos de latitud y longitud en cadenas que representan un hexágono único, según la resolución especificada. Realicemos esta operación en toda la base de datos de instalaciones y también convirtamos las cadenas de hexágonos en polígonos:
Una pregunta que a menudo surge en estos proyectos de análisis de datos espaciales es cuántos proyectos en los hexágonos se clasifican por alguna columna, digamos “agencia”. Afortunadamente, esto es muy fácil de calcular y visualizar ahora que tenemos los datos agrupados en hexágonos H3:
En este caso, puedes ver que las agencias DCAS (Departamento de Servicios Administrativos de la Ciudad) y PARKS (Departamento de Parques y Recreación) son las dos agencias con más instalaciones por cada hexágono. Esto probablemente tenga sentido ya que estas dos agencias tendrían más instalaciones físicas (piensa en edificios administrativos o áreas recreativas como parques).
Conclusión
Los índices espaciales, como viste, son herramientas de optimización muy útiles para la ciencia de datos y el análisis geoespacial. En el caso de una consulta de intersección simple, el uso de un índice espacial mejora drásticamente el rendimiento de la consulta en comparación con la función de intersección estándar de GeoPandas. Hubo muchos matices en cuanto a cómo se implementa este índice, así como sus implicaciones, como tener grandes ramas de datos agrupados. Como vimos, las empresas han desarrollado sus propias soluciones: un ejemplo es el índice de código abierto H3 de Uber, que nos permite responder diversas preguntas de análisis espacial. Si bien demostré una operación de recuento de instalaciones basada en la agencia, H3 brinda una base para otras aplicaciones de aprendizaje automático más complejas.
Si te gusta este tipo de contenido pero quieres aprender más ampliamente sobre tecnología de planificación urbana, también escribo un boletín llamado “The Zoned Out Chronicles”. ¡Te animo a que lo revises!
¡Gracias por leer!
