Compact structures for the representation of trajectory information

Abstract

[Abstract] We live in an age of information and movement. Constantly on the move, tethered to our cell phones, searching the Internet for directions to the station, what time the next bus stops, what is the best route to the mall, where we are going to eat today, and so on. We get up and go to work or school, we go home, we go out partying... As a species it would seem that we are incapable of sitting still for long, we always yearn to get somewhere. Essentially none of this is new, nor should it be considered unique to the current age. They already used maps in ancient Babylon. What they didn’t have, however, were screens, and the whole parade of technologies that in the 21st century has become practically a new limb for citizens of developed countries. Those smartphones, those GPS, the reader of our traveler card on the bus, are systems that collect information about us; about how we move. Facilities such as shopping malls or hospitals can easily capture with technological solutions the movements of users and staff, but even indirectly, when making a card payment, or, again, validating a trip on a means of public transport with a traveler card, we are creating a record of our position and intention to move at a given instant of time. We are not talking about discrete amounts of information, either. With so much technology flooding us, it is to be expected that the positioning information of people and objects over a relatively large period of time (or even not that large, depending on the context) will reach massive sizes. Of course, any technological advance brings with it ripe opportunities for research on how to refine the new technologies and apply them to solve problems that matter to people and society at large. Thus, this thesis focuses on researching solutions for the representation of maps and the movements of people and objects on those maps over time. Our work focuses on facilitating the spatially and time-efficient representation of maps and trajectories using compact data structures capable of storing information in a compressed format while allowing its exploitation without the need for decompression. Our first contribution is a strategy for representing maps at different scales or zoom levels in a compact manner. Most systems that work with maps, such as Google Maps, store different versions of the same map at different levels of detail suitable for different zoom levels. This generates redundant information that needs to be stored. This is because, for example, although a coastline may look much more simplified at a low zoom, using far fewer geographic points than at a high zoom, the visible points will still exist at all successive zoom levels as well, only added to new points that provide more detail to the shape. Our proposal can represent different zoom levels without repeating any geographic points between them, thus greatly improving storage size when compared to typical solutions. Our second contribution is an indoor positioning system, capable of capturing user trajectories in a semantically annotated, motion-limited space (e.g., a shopping mall or medical facility where the layout of the space informs the possibilities of movement and it is possible to tag rooms and corridor segments with unique identifiers), and compressing them into a compact data structure with access times to the movements of any user in a given time period well below a millisecond. Finally, the last contribution of this thesis is the work done as part of an ambitious research project aimed at the analysis and exploitation of traveler movements in public transport networks. Using traveler card records, we offer solutions for storing and exploiting trips from an origin to a destination stop of users of the transport network.

[Resumen] Vivimos en la era de la información y el movimiento. Constantemente en movimiento, enganchados a nuestros teléfonos móviles, buscando en Internet cómo llegar a la estación, a qué hora pasa el bus, cuál es la mejor ruta hasta el centro comercial, dónde vamos a comer hoy, etc. Nos levantamos y vamos al trabajo o a la escuela, volvemos a casa, salimos de fiesta. . . Como especie parecería que somos incapaces de permanecer quietos mucho tiempo, siempre anhelamos llegar a alguna parte. En esencia nada de esto es nuevo, ni deberían considerarse circunstancias exclusivas de la era actual. Ya se usaban mapas en la antigua Babilonia. No obstante, lo que no tenían eran pantallas, y todo el desfile de tecnologías que en el siglo 21 se han convertido en prácticamente una nueva extremidad para los ciudadanos de los países desarrollados. Los teléfonos inteligentes, los GPS, el lector de nuestra tarjeta de viajero en el autobús; son todos sistemas que recaban información sobre nosotros, sobre cómo nos movemos. Instalaciones como centros comerciales u hospitales pueden utilizar soluciones tecnológicas para conocer los movimientos de usuarios y personal con facilidad, pero, incluso de forma indirecta, al hacer un pago con tarjeta de crédito, o, de nuevo, al validar un viaje en un medio de transporte público con una tarjeta de viajero, estamos creando un registro, tanto de nuestra posición como de una intención de desplazamiento, en un instante de tiempo determinado. Por descontado, no estamos hablando de cantidades de información precisamente pequeñas. Con tanta tecnología inundando nuestras vidas, es de esperar que la información de posicionamiento de personas y objetos a lo largo de un periodo de tiempo relativamente grande (o no tan grande, esto depende del contexto) alcance tamaños masivos. Por supuesto, cualquier avance tecnológico trae consigo oportunidades de investigación en como afinar las nuevas tecnologías y aplicarlas para resolver problemas que importan a las personas y a la sociedad en general. Así pues, esta tesis se centra en investigar soluciones para la representación de mapas y los movimientos de personas y objetos en esos mapas. El trabajo realizado se centra en facilitar la representación eficiente, tanto desde el punto de vista espacial como del tiempo de acceso a los datos, de mapas y trayectorias, utilizando estructuras de datos compactas que almacenan la información en formato comprimido a la vez que permiten su explotación sin necesidad de un proceso previo de descompresión. Nuestra primera contribución es una estrategia para la representación de mapas a diferentes niveles de escala o zoom de forma compacta. La mayoría de sistemas que trabajan con mapas, como Google Maps y similares, guardan diferentes versiones de un mismo mapa a diferentes niveles de detalle adecuados para los distintos niveles de zoom. Esto genera una gran cantidad de información redundante que es necesario almacenar. Esto es debido a que, por ejemplo, aunque la línea de una costa se vea mucho más simplificada a un zoom bajo, utilizando muchos menos puntos geográficos que en un zoom alto, los puntos que sí se ven van a existir en todos los niveles sucesivos de zoom también, solo que sumados a nuevos puntos que confieren más detalle a la forma. Nuestra propuesta es capaz de representar diferentes niveles de zoom sin repetir ningún punto geográfico entre ellos, mejorando por tanto en términos de espacio de almacenamiento respecto a las soluciones típicas. Nuestra segunda contribución es un sistema de posicionamiento en interiores capaz de capturar las trayectorias de usuarios en un espacio con movimiento limitado y anotado semánticamente (por ejemplo, un centro comercial o instalación médica donde la distribución del espacio informa obviamente de las posibilidades de movimiento y es posible etiquetar salas y segmentos de pasillo con identificadores únicos), y comprimirlas en una estructura de datos compacta con tiempos de acceso a los movimientos de cualquier usuario en un periodo de tiempo determinado muy por debajo del milisegundo. Finalmente, la última contribución de esta tesis es el trabajo realizado como parte de un ambicioso proyecto de investigación destinado al análisis y explotación de los movimientos de viajeros en redes de transporte público. Utilizando registros de tarjetas de viajero, ofrecemos soluciones para almacenar y explotar los viajes de una parada de origen a otra de destino de usuarios de la red de transporte.

[Resumo] Vivimos nunha era de información e movemento. Constantemente en movemento, atados aos nosos móbiles, buscando en Internet como chegar á estación, a que hora pasa o autobús, cal é a mellor ruta para ir ao centro comercial, onde imos comer hoxe, etc. Levantámonos e imos ao traballo ou ao colexio, chegamos á casa, saímos de festa... Como especie parece que somos incapaces de quedarnos moito tempo parados, sempre queremos chegar a algún sitio. En esencia nada disto é novo, nin debe ser visto como exclusivo da época actual. Xa usaban mapas na antiga Babilonia. Porén, o que non tiñan eran pantallas, e todo o desfile de tecnoloxías que no século XXI se converteron practicamente nunha nova extremidade para os cidadáns dos países desenvolvidos. Os móbiles intelixentes, os GPS, o lector da nosa tarxeta de viaxeiro no autobús, son sistemas que recollen información sobre nós; sobre como nos movemos. Instalacións como centros comerciais ou hospitais poden coñecer con solucións tecnolóxicas os movementos de usuarios e persoal con facilidade, pero, incluso indirectamente, realizando o pago con tarxeta, ou, de novo, validando unha viaxe nun medio de transporte público con nosa tarxeta de viaxeiro, estamos creando un rexistro da nosa posición e intención de movernos nun momento dado. Ademais, non estamos a falar de cantidades de información precisamente pequenas. Con tanta tecnoloxía que nos inunda, é de esperar que a información de posicionamento de persoas e obxectos durante un período de tempo relativamente grande (ou non tan grande, dependendo do contexto) alcance tamaños masivos. Por suposto, calquera avance tecnolóxico trae consigo oportunidades de investigación sobre como mellorar as novas tecnoloxías e aplicalas para resolver problemas que importan ás persoas e a sociedade en xeral. Así, esta tese céntrase en investigar solucións para a representación de mapas e os movementos de persoas e obxectos neses mapas ao longo do tempo. O traballo realizado céntrase en facilitar a representación eficiente, tanto dende o punto de vista espacial como no tempo de acceso aos datos, de mapas e traxectorias, utilizando estruturas de datos compactas que almacenan a información nun formato comprimido ao tempo que permiten a súa explotación sen necesidade de un proceso de descompresión previo. A nosa primeira contribución é unha estratexia para representar mapas a diferentes escalas ou niveis de zoom dun xeito compacto. A maioría dos sistemas que traballan con mapas, como Google Maps e similares, gardan diferentes versións do mesmo mapa en diferentes niveis de detalle pensados para diferentes niveis de zoom. Isto xera unha gran cantidade de información redundante que é necesario almacenar. Isto ocorre porque, por exemplo, aínda que unha liña de costa parece moito máis simplificada cun zoom baixo, utilizando moitos menos puntos xeográficos que cun zoom alto, os puntos visibles existirán en todos os niveis de zoom sucesivos. Ao aumentar o zoom, só se engadirán aos novos puntos que dan máis detalle á forma. A nosa proposta é capaz de representar diferentes niveis de zoom sen repetir ningún punto xeográfico entre eles, mellorando moito o almacenamento en comparación coas solucións típicas. A nosa segunda contribución é un sistema de posicionamento en interiores, capaz de captar as traxectorias dos usuarios nun espazo de movemento limitado e anotado semanticamente (por exemplo, un centro comercial ou centro médico onde a distribución do espazo informa obviamente das posibilidades de movemento e os cuartos e os segmentos do corredor pódense etiquetar con identificadores únicos) e comprimirse nunha estrutura de datos compacta con tempos de acceso aos movementos de calquera usuario nun período de tempo determinado moi por debaixo do milisegundo. Finalmente, a última contribución desta tese é o traballo realizado no marco dun ambicioso proxecto de investigación enfocado á análise e explotación dos movementos de viaxeiros nas redes de transporte público. Mediante os rexistros da tarxeta de viaxeiro, ofrecemos solucións para almacenar e explotar viaxes dunha parada de orixe a outra de destino dos usuarios da rede de transporte.