No description available.

No description available.

For operational and planning purposes it is important to observe, predict and monitor the traffic performance of congested urban road links and networks. This monitoring effort describes the traffic conditions in road networks using congestion performance measures. The objective of this research is to analyse and evaluate methods for measuring congestion and congestion performance measures for monitoring purposes. For this objective, a selection of the required aspects of the performance measures in the literature is considered. The aspects to be considered can be classified into two categories: A first group relates to the statistical aspects of these indicators, i.e. reliability. The second relates to their ability to capture the impacts of congestion, i.e .relevance. The reliability and relevance of the congestion performance measures are evaluated. A recommendation of the most suitable indicator is provided at the end of the study. / QC 20110912

Moving objects database systems are the most challenging sub-category among Spatio-Temporal database systems. A database system that updates in real-time the location information of GPS-equipped moving vehicles has to meet even stricter requirements. Currently existing data storage models and indexing mechanisms work well only when the number of moving objects in the system is relatively small. This dissertation research aimed at the real-time tracking and history retrieval of massive numbers of vehicles moving on road networks. A total solution has been provided for the real-time update of the vehicles’ location and motion information, range queries on current and history data, and prediction of vehicles’ movement in the near future. To achieve these goals, a new approach called Segmented Time Associated to Partitioned Space (STAPS) was first proposed in this dissertation for building and manipulating the indexing structures for moving objects databases. Applying the STAPS approach, an indexing structure of associating a time interval tree to each road segment was developed for real-time database systems of vehicles moving on road networks. The indexing structure uses affordable storage to support real-time data updates and efficient query processing. The data update and query processing performance it provides is consistent without restrictions such as a time window or assuming linear moving trajectories. An application system design based on distributed system architecture with centralized organization was developed to maximally support the proposed data and indexing structures. The suggested system architecture is highly scalable and flexible. Finally, based on a real-world application model of vehicles moving in region-wide, main issues on the implementation of such a system were addressed.

Spatial and topological features of urban road networks have been observed variously in the past. No previous study, however, has investigated and compared an extensive data set from cities all over the world regarding their network properties. In this work, re-spectively 20 large cities from 5 continents and Germany are analyzed. In the process, node degree, link length, shortest paths, detour index as well as measures for rectangu-larity are used to characterize and to differentiate the networks. While most networks properties are quite diverse from continent to continent, the detour index as a measure of efficiency shows remarkable similarities and homogeneity over all regions, independ-ent of their spatial network structure. It is shown that in some cities this efficiency is mainly sustained by a subnetwork of major roads, while in others it relies on a balance between minor and major roads. Rectangularity in all regions is shown to be predomi-nant in the structure of minor road subnetworks, while it is shown that this feature is not trivially connected to the node degree. / Räumliche und topografische Eigenschaften urbaner Straßennetzwerke sind in der Ver-gangenheit vielfältig untersucht wurden. Keine der bisherigen Studien hat jedoch eine umfassende Anzahl weltweiter Städte auf ihre Netzwerkeigenschaften untersucht. In dieser Arbeit werden jeweils 20 Großstädte aus 5 Kontinenten analysiert. Knotengrad, Kantenlängen, kürzeste Pfade, Detour Index sowie die Rechtwinkligkeit werden schritt-weise untersucht, um die Netzwerke zu charakterisieren und voneinander zu differen-zieren. Während die meisten Netzwerkmaße große Unterscheide von Kontinent zu Kon-tinent aufweisen, lassen sich beim Detour Index, welcher ein Maß für die Effizienz im Netzwerk dient, bemerkenswerte Gemeinsamkeiten in allen Regionen unabhängig von der räumlichen Netzwerkstruktur feststellen. Es wird gezeigt, dass die Effizienz in eini-gen Städten hauptsächlich durch ein Teilnetz von Hauptstraßen getragen wird, während sie anderswo auf einer Balance zwischen Haupt- und Nebenstraßen beruht. Vor allem in der Struktur von Nebenstraßennetzwerken kann Rechtwinkligkeit festgestellt werden, während gleichzeitig wird, dass letztere in keinem trivialen Zusammenhang mit dem Knotengrad steht.

The proliferation of mobile devices and advances in geo-positioning technologies has fueled the growth of location-based applications, systems and services. Many location-based applications have now gained high popularity and permeated the daily activities of mobile users. This has led to a huge amount of geo-location data generated on a daily basis, which draws significant interests in analyzing and mining ubiquitous location data, especially trajectories of mobile objects moving in road networks (MO trajectories). Mobile trajectories are complex spatio-temporal sequences of location points with varying sample sizes and varying lengths. Mining interesting patterns from large collection of complex MO trajectories presents interesting challenges and opportunities which can reveal valuable insights to the studies of human mobility in many perspectives. This dissertation research contributes original ideas and innovative techniques for mining complex trajectories from whole trajectories, from subtrajectories of significant characteristics, and from semantic location sequences within large-scale datasets of MO trajectories. Concretely, the first unique contribution of this dissertation is the development of NEAT, a three-phase road-network aware trajectory clustering framework to organize MO subtrajectories into spatial clusters representing highly dense and highly continuous traffic flows in a road network. Compared with existing trajectory clustering approaches, NEAT yields highly accurate clustering results and runs orders of magnitude faster by smartly utilizing traffic locality with respect to physical constraints of the road network, traffic flows among consecutive road segments and flow-based density of mobile traffic as well as road network based distances. The second original contribution of this dissertation is the design and development of TraceMob, a methodical and high performance framework for clustering whole trajectories of mobile objects. To our best knowledge, this is the first whole trajectory clustering system for MO trajectories in road networks. The core idea of TraceMob is to develop a road-network aware transformation algorithm that can map complex trajectories of varying lengths from a road network space into a multidimensional data space while preserving the relative distances between complex trajectories in the transformed metric space. The third novel contribution is the design and implementation of a fast and effective trajectory pattern mining algorithm TrajPod. TrajPod can extract the complete set of frequent trajectory patterns from large-scale trajectory datasets by utilizing space-efficient data structures and locality-aware spatial and temporal correlations for computational efficiency. A comprehensive performance study shows that TrajPod outperforms existing sequential pattern mining algorithms by an order of magnitude.

Spatial and topological features of urban road networks have been observed variously in the past. No previous study, however, has investigated and compared an extensive data set from cities all over the world regarding their network properties. In this work, re-spectively 20 large cities from 5 continents and Germany are analyzed. In the process, node degree, link length, shortest paths, detour index as well as measures for rectangu-larity are used to characterize and to differentiate the networks. While most networks properties are quite diverse from continent to continent, the detour index as a measure of efficiency shows remarkable similarities and homogeneity over all regions, independ-ent of their spatial network structure. It is shown that in some cities this efficiency is mainly sustained by a subnetwork of major roads, while in others it relies on a balance between minor and major roads. Rectangularity in all regions is shown to be predomi-nant in the structure of minor road subnetworks, while it is shown that this feature is not trivially connected to the node degree.:Table of Contents List of Figures V List of Tables VI Chapter 1 Introduction 1 Chapter 2 Preliminaries 4 2.1 Complex Networks 4 2.2 Network Characteristics 5 2.2.1 Node Degree 5 2.2.2 Link Length 6 2.2.3 Shortest Path Length 7 2.2.4 Detour Index 7 2.2.5 Rectangularity 8 2.3 Data 11 2.3.1 Data Source and Analyzed Cities 11 2.3.2 Data Structure 12 2.3.3 Data Quality 14 2.4 Data Preprocessing 15 2.4.1 Removal of Dead Ends 16 2.4.2 Removal of Transient Nodes 17 2.4.3 Merging of Multi-Node Intersections and Roads with Separated Lanes 17 2.5 Network Modifications 20 Chapter 3 Results and Discussion 23 3.1 Unmodified Networks 23 3.1.1 Node Degree 23 3.1.2 Link Length 25 3.1.3 Network Efficiency 28 3.1.4 Rectangularity 30 3.2 Modified Networks and Comparison to Unmodified Networks 36 3.2.1 Node Degree 37 3.2.2 Link Length 39 3.2.3 Network Efficiency 41 3.2.4 Rectangularity 46 Chapter 4 Conclusion and Outlook 49 References 51 Appendix A Detailed Results of Unmodified Networks 55 Appendix A.1 Europe 55 Appendix A.2 Anglo America 56 Appendix A.3 Latin America 57 Appendix A.4 Asia 58 Appendix A.5 Africa 59 Appendix A.6 Germany 60 Appendix B Corrupted Networks due to Merging of Intersections with Radius 50 m 61 Appendix C Modification 2 62 Appendix D Spatial Distributions of Network Measures 63 Appendix D.1 Node Degree 63 Appendix D.2 Link Length 64 Appendix D.3 Detour Index 65 Appendix D.4 Rectangularity 66 Appendix E Detailed results of modified networks 67 Appendix E.1 Europe 67 Appendix E.2 Anglo America 68 Appendix E.3 Latin America 69 Appendix E.4 Asia 70 Appendix E.5 Africa 71 Appendix E.6 Germany 72 / Räumliche und topografische Eigenschaften urbaner Straßennetzwerke sind in der Ver-gangenheit vielfältig untersucht wurden. Keine der bisherigen Studien hat jedoch eine umfassende Anzahl weltweiter Städte auf ihre Netzwerkeigenschaften untersucht. In dieser Arbeit werden jeweils 20 Großstädte aus 5 Kontinenten analysiert. Knotengrad, Kantenlängen, kürzeste Pfade, Detour Index sowie die Rechtwinkligkeit werden schritt-weise untersucht, um die Netzwerke zu charakterisieren und voneinander zu differen-zieren. Während die meisten Netzwerkmaße große Unterscheide von Kontinent zu Kon-tinent aufweisen, lassen sich beim Detour Index, welcher ein Maß für die Effizienz im Netzwerk dient, bemerkenswerte Gemeinsamkeiten in allen Regionen unabhängig von der räumlichen Netzwerkstruktur feststellen. Es wird gezeigt, dass die Effizienz in eini-gen Städten hauptsächlich durch ein Teilnetz von Hauptstraßen getragen wird, während sie anderswo auf einer Balance zwischen Haupt- und Nebenstraßen beruht. Vor allem in der Struktur von Nebenstraßennetzwerken kann Rechtwinkligkeit festgestellt werden, während gleichzeitig wird, dass letztere in keinem trivialen Zusammenhang mit dem Knotengrad steht.:Table of Contents List of Figures V List of Tables VI Chapter 1 Introduction 1 Chapter 2 Preliminaries 4 2.1 Complex Networks 4 2.2 Network Characteristics 5 2.2.1 Node Degree 5 2.2.2 Link Length 6 2.2.3 Shortest Path Length 7 2.2.4 Detour Index 7 2.2.5 Rectangularity 8 2.3 Data 11 2.3.1 Data Source and Analyzed Cities 11 2.3.2 Data Structure 12 2.3.3 Data Quality 14 2.4 Data Preprocessing 15 2.4.1 Removal of Dead Ends 16 2.4.2 Removal of Transient Nodes 17 2.4.3 Merging of Multi-Node Intersections and Roads with Separated Lanes 17 2.5 Network Modifications 20 Chapter 3 Results and Discussion 23 3.1 Unmodified Networks 23 3.1.1 Node Degree 23 3.1.2 Link Length 25 3.1.3 Network Efficiency 28 3.1.4 Rectangularity 30 3.2 Modified Networks and Comparison to Unmodified Networks 36 3.2.1 Node Degree 37 3.2.2 Link Length 39 3.2.3 Network Efficiency 41 3.2.4 Rectangularity 46 Chapter 4 Conclusion and Outlook 49 References 51 Appendix A Detailed Results of Unmodified Networks 55 Appendix A.1 Europe 55 Appendix A.2 Anglo America 56 Appendix A.3 Latin America 57 Appendix A.4 Asia 58 Appendix A.5 Africa 59 Appendix A.6 Germany 60 Appendix B Corrupted Networks due to Merging of Intersections with Radius 50 m 61 Appendix C Modification 2 62 Appendix D Spatial Distributions of Network Measures 63 Appendix D.1 Node Degree 63 Appendix D.2 Link Length 64 Appendix D.3 Detour Index 65 Appendix D.4 Rectangularity 66 Appendix E Detailed results of modified networks 67 Appendix E.1 Europe 67 Appendix E.2 Anglo America 68 Appendix E.3 Latin America 69 Appendix E.4 Asia 70 Appendix E.5 Africa 71 Appendix E.6 Germany 72

No description available.

Regular path queries (RPQs), expressed as regular expressions over the alphabet of database edge-labels, are commonly used for guided navigation of graph databases. RPQs are the basic building block of almost all the query languages for graph databases, providing the user with a nice and simple way to express recursion. While convenient to use, RPQs are notorious for their high computational demand. Except for few theoretical works, there has been little work evaluating RPQs on databases of great practical interest, such as large spatial networks. In this thesis, we present a grid-aware, fault tolerant distributed algorithm for answering RPQs on spatial networks. We engineer each part of the algorithm to account for the assumed computational-grid setting. We experimentally evaluate our algorithm, and show that for typical user queries, our algorithm satisfies the desiderata for distributed computing in general, and computational-grids in particular.

Network mapping is used to extract the coordinates of a network's components in an image. Furthermore, machine learning algorithms have demonstrated their efficacy in advancing the field of network mapping across various domains, including mapping of road networks and blood vessel networks. However, accurately mapping of road networks still remains a challenge due to difficulties in identification and separation of roads in the presence of occlusion caused by trees, as well as complex environments, such as parking lots and complex intersections. Additionally, the segmentation of blood vessels networks, such as the ones in the retina, is also not trivial due to their complex shape and thin appearance. Therefore, the aim for this thesis was to investigate two deep learning approaches to improve mapping of networks, namely by refining existing road network probability maps, and by estimating road network orientations. Additionally, the thesis explores the possibility of using a machine learning model trained on road network probability maps to refine retina network segmentations. In the first approach, U-Net models with a binary output channel were implemented to refine existing probability maps of networks. In the second approach, ResNet models with a regression output were implemented to estimate the orientation of roads within a network. The models for refining road network probability maps were evaluated using F1-score and MCC-score, while the models for estimating road network orientation were evaluated based on angle loss, angle difference, F1-score, and MCC-score.  The results for refining road segmentations yielded an increase of 0.102 MCC-score compared to the baseline (0.701). However, when applying the segmentation refinement model to retina images, the output from the model achieved merely 0.226 in MCC-score. Nevertheless, the model demonstrated the capability to identify and refine the segmentation of large blood vessels. Additionally, the estimation of road network orientation achieved an average error of 10.50 degrees. It successfully distinguished roads from the background, achieving an MCC-score of 0.805. In conclusion, this thesis shows that a deep learning-based approach for road segmentation refinement is beneficial, especially in cases where occlusions are present. However, the refinement of retina image segmentations using a model trained on roads and tested on retina images produced unsatisfactory results, likely due to differences in scale between road width and vessel size. Further experiments with adjustments in image scales are likely needed to achieve better results. Moreover, the orientation model demonstrated promising results in estimating the orientation of road pixels and effectively differentiating between road and non-road pixels.