Compressed data structures for trajectory representation

Resumen

La proliferación de por un lado de dispositivos GPS en smartphones, vehículos o pulseras de deporte, y por otro, de otros mecanismos de geolocalización (como las tarjetas de pago de trasporte público), han generado una capacidad inédita de obtener y almacenar las trayectorias que generan las personas al moverse durante sus quehaceres diarios. Sin embargo, no existen modelos de datos estándar para representar dichas trayectorias, además de que ni las bases de datos tradicionales, ni para las nuevas bases de datos NoSQL se adecúan bien a la representación y explotación de esos datos complejos de naturaleza espacio-temporal que son las trayectorias. Para hacer más complejo aún el panorama, se constata además que cuando se quieren almacenar trayectorias de viajeros de transporte público, o de clientes en centros comerciales, o simplemente de personas o vehículos moviéndose por la ciudad hay que enfrentarse a un verdadero escenario Big Data en el que la eficiencia en la respuesta a las consultas se hace muy difícil. Por todo ello, en esta tesis se aborda el diseño de estructuras de datos compactas para la representación de las trayectorias seguidas, por un lado, por vehículos y/o personas que se mueven por las calles de un entorno urbano o periurbano acotado, y por otro los itinerarios de viajeros de transporte público. Además de diseñar esas estructuras de datos compactas, que permiten representar ese escenario Big Data habitual en estos dominios de aplicación, se han diseñado los algoritmos que permiten la explotación eficiente de dichos datos. Dichos algoritmos, además de resolver las consultas espacio-temporales clásicas, tanto las de posición de un objeto en un tiempo, o trayectoria de un objeto durante un intervalo temporal, como las consultas de rango espacio-temporal (qué objetos están en una ventana del espacio en un instante o intervalo temporal) resuelven también consultas más especializadas para el análisis de trayectorias de viajeros. Por ejemplo, hemos diseñado algoritmos para consultar el número de viajeros que inician (o terminan) su viaje en cierto lugar dentro de un cierto intervalo temporal, o el número de viajeros que conmutan de una línea a otra de la red de transporte público en una cierta parada, o incluso el número de viajeros que inicia su viaje en cierto lugar (parada o barrio) y lo termina en otra parada o barrio determinados. Tanto las estructuras de datos diseñadas como todos los algoritmos de consulta, que están disponibles en https://github.com/dgalaktionov/compact-trip-representation, han sido evaluados experimentalmente. Con estas estructuras es posible representar en un espacio de 100 MiB una colección de aproximadamente un millón y medio de trayectorias de taxis, o alternativamente diez millones de trayectorias consistentes de itinerarios sobre redes de transporte público, al ser éstas últimas más compactas. En ambos casos, podemos resolver la mayor parte de las consultas de explotación planteadas en el orden de microsegundos, con algoritmos que escalan de forma logarítmica con respecto al incremento en el número de trayectorias almacenadas. Por último y dado el carácter de tesis industrial de este trabajo, era necesario que la investigación realizada tuviese un carácter claramente aplicado, por ello se implementó una aplicación web con tecnología de Sistemas de Información Geográfica que en vez de trabajar sobre una base de datos espacial convencional utiliza la estructura comprimida y los algoritmos para su explotación diseñados en la tesis. Esa aplicación facilita, mediante una sencilla e intuitiva interfaz de usuario que representa el mapa de la red de transporte, el lanzamiento de los algoritmos diseñados sobre un amplio conjunto de trayectorias de viajeros. Del mismo modo esa interfaz presenta los resultados de las consultas de modo gráfico e intuitivo.