[en] The proliferation of GPS devices in smartphones, vehicles and sport wearables in one hand, and geolocation mechanisms (such as smart cards in public transportation) in the other hand, have produced an unprecedented capacity of obtaining and storing trajectories that people generate by the movements that originate from their daily schedules. However, no standard data models exist to represent these trajectories, and besides neither traditional databases nor new NoSQL databases are adequate for the representation and exploitation of the complex data of spatio-temporal nature which these trajectories consist of. This general outlook is even more complex once we consider that whenever we are storing information related to a context of public transportation passengers, customers inside a mall, or simply vehicles moving in a city we must deal with a true Big Data scenario in which guaranteeing an efficient response can be very challenging. Consequently, in this thesis we address the design of compact data structures for the representation of the followed trajectories, both in the context of vehicles and/or people moving in urban or periurban spaces, as in the context of itineraries of commuters in public transportation. Additionally to designing these compact data structures that allow us to represent the Big Data scenario usually seen in this application domain, we have designed the algorithms that allow the efficient exploitation of said information. These algorithms, in addition to solving classic spatio-temporal queries, such as obtaining the position of a moving object at a time instant, reconstructing the trajectory of an object, or even spatio-temporal window queries (which objects are inside a spatial range either within a time window or at a time instant), are also able to solve more specialized queries for the analysis of trajectories that travelers make. For instance, we have designed algorithms to query the number of travelers that start (or finish) their trip in a certain place within a determined time interval, or the number of travelers that switch from one line from the public transportation network to another using a particular stop, or even the number of travelers that had started their trip in a certain place (which can be either a stop or a whole neighborhood) to finish it in another place. Both the designed structures as the querying algorithms, which are available at https://github.com/dgalaktionov/compact-trip-representation, have been experimentally evaluated. With these structures we are able to represent, in a compact space of 100 MiB, a collection of approximately a million and a half of taxi trajectories, or alternatively ten million trajectories consisting of itineraries over public transportation networks, given that they are more compact. In both cases, we can solve most of the considered exploitation queries in the order of microseconds, with algorithms that scale logarithmically with respect to the increase in the number of stored trajectories. Finally, considering the practical quality of this work, it was required for the performed research to be of a clearly applied nature, which led us to developing a web application with Geograhic Information Systems technology, which integrates with our compressed structures and algorithms instead of relying on common spatial databases. This application, which provides a simple and intuitive user interface that represents the map of a transportation network, enabled an end user to run the aforementioned algorithms over a large collection of historic trajectories. Likewise, this interface presents the query results in a graphical and intuitive way.

[gl] A proliferación de por un lado os dispositivos GPS en smartphones, vehículos ou brazaletes deportivos e por outro lado os mecanismos de xeolocalización (como as tarxetas de pago do transporte público), xeraron unha capacidade sen precedentes para obter e almacenar as traxectorias que a xente xera ao moverse durante as súas tarefas diarias. Non obstante, non hai modelos de datos estándar para representar tales traxectorias, ademais de que nin as bases de datos tradicionais nin para as novas bases de datos NoSQL son adecuadas para a representación e explotación de datos tan complexos de natureza espazo-temporal que son as traxectorias. Para facer o panorama aínda máis complexo, tamén se comproba que cando se quere almacenar traxectorias de viaxeiros de transporte público, ou clientes en centros comerciais, ou simplemente de persoas ou vehículos que se desprazan pola cidade, se ten que afrontar un verdadeiro escenario de Big Data no que a eficiencia na resposta ás consultas faise moi difícil. Por iso, esta tese trata do deseño de estruturas compactas de datos para a representación dos camiños seguidos, por un lado, por vehículos e/ou persoas que se desprazan polas rúas dun contorno urbano ou periurbano delimitado, e por outros itinerarios de viaxeiros en transporte público. Ademais de deseñar estas estruturas compactas de datos, que permiten representar ese escenario Big Data habitual neste dominios de aplicación, deseñáronse algoritmos que permitan a explotación eficiente dos devanditos datos. Estes algoritmos, ademais de resolver as clásicas consultas espazo-temporais, tanto a posición dun obxecto á vez, como a traxectoria dun obxecto durante un intervalo de tempo, así como as consultas de rango espazo-temporal (qué obxectos están nun rango do espazo nun intre ou nun intervalo temporal) tamén resolver consultas máis especializadas para a análise de traxectorias de viaxeiros. Por exemplo, deseñamos algoritmos para comprobar o número de viaxeiros que inician (ou terminan) a súa viaxe nun determinado lugar nun determinado intervalo de tempo, ou o número de viaxeiros que cambian dunha liña a outra da rede de transporte público nun certa parada, ou incluso o número de viaxeiros que comezan a súa viaxe nun determinado lugar (parada ou barrio) e rematan noutra parada ou barrio específico. Tanto as estruturas de datos deseñadas como todos os algoritmos de consulta, dispoñibles en https://github.com/dgalaktionov/ compact-trip-representation, foron evaluados experimentalmente. Con estas estruturas é posible representar nun espazo de 100 MiB unha colección de aproximadamente un millón e medio de traxectos de taxi ou, alternativamente, dez millóns de traxectos consistentes en itinerarios en redes de transporte público, sendo estes últimos máis compactos. Nos dous casos, podemos resolver a maioría das consultas de explotación plantexadas na orde de microsegundos, con algoritmos que escalan logarítmicamente con respecto ao aumento do número de traxectorias almacenadas. Finalmente, dado o carácter de tese industrial deste traballo, foi necesario que a investigación realizada tivese un carácter claramente aplicado, polo que se implementou unha aplicación web con tecnoloxía de Sistemas de Información Xeográfica que no canto de traballar nunha base de datos espacial convencional usa a estrutura comprimida e algoritmos de explotación deseñados na tese. Esta aplicación facilita, mediante unha interface de usuario sinxela e intuitiva que representa o mapa da rede de transporte, o lanzamento dos algoritmos deseñados nun amplo conxunto de rutas de pasaxeiros. Do mesmo xeito que a interface presenta os resultados das consultas dun xeito gráfico e intuitivo.