Author:

Keywords:

Itec, iMinds

Abstract:

The present thesis describes various applications based on concrete questions originating from GIS practice. It aims at the design and validation of (1) methods to maintain the quality of large amounts of geographical data, and, (2) service components for spatial networks, dealing with efficiency in environments with a limited amount of resources.In the first place, such an endeavour involves quality maintenance in geographic information systems (GIS). It is pursued through the identification of patterns, describing relational regularities, and corresponding outliers indicating probable inconsistencies in the data. This approach is different from classical approaches to outlier detection and quality analysis in GIS, traditionally relying on techniques prospecting for statistical and positional deviation in geographical data.It moreover implies the efficiency enhancement of shortest path (cost) approximation components through auxiliary structures in spatial weighted graphs. Efficiency in this context mainly refers to the approximation accuracy, the calculation time required to produce an approximation and the structures' compactness. A first part describes the integration of a hierarchical shortest path algorithm in a multi-tier architecture, considerably restricting the amount of data used during a routing query. Secondly, an evaluation framework for approximate distance oracles is introduced, taking into account the overall accuracy performance of the oracle. An advanced oracle, based on graph partitioning and minimizing the absolute approximation error in spatial graphs, is presented and evaluated.The fast automated discovery of attractive closed paths in graphs comprises the third theme of this work. This problem arises from the introduction of edge attractiveness scores in graphs. The tour suggestion problem for outdoor activities aims at optimizing the arc and vertex attractiveness of a closed path in a transportation network graph, satisfying a set of constraints. An algorithm of low computational impact generating heuristic solutions to this problem is presented.The underlying concepts and approaches introduced in the present thesis are applicable in more general domains. The approach to relational outlier detection applies to quality maintenance in data-rich intelligent systems. The auxiliary structures enhancing efficiency of approximative shortest path algorithms can be reused for exact algorithms. The automated discovery of structures of high attractiveness is valuable for a broader class of applications in graphs with dually weighted edges. Four software components resulting from this research have been adopted by industry.