Compressed data structures for trajectory representation

Resumen

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.