Fakultät für Mathematik, Informatik und Statistik - Digitale Hochschulschriften der LMU - Teil 01/02 Archiv

In this thesis we study convex subcomplexes of spherical buildings. In particular, we are interested in a question of J. Tits which goes back to the 50’s, the so-called Center Conjecture. It states that a convex subcomplex of a spherical building is a subbuilding or the building automorphisms preserving the subcomplex have a common fixed point in it. A proof of the Center Conjecture for the buildings of classical types (An, Bn and Dn) has been given by B. Muehlherr and J. Tits in [MT06]. The F4-case was presented by C. Parker and K. Tent in a talk in Oberwolfach [PT08]. Both approaches use combinatorial methods from incidence geometry. B. Leeb and the author gave in [LR09] differentialgeometric proofs for the cases F4 and E6 from the point of view of the theory of metric spaces with curvature bounded from above. In this work we develop the differential-geometric approach further. Our main result is the proof of the Center Conjecture for buildings of type E7 and E8, whose geometry is considerably more complicated. In particular, this completes the proof of the Center Conjecture for all thick spherical buildings. We also give a short differential-geometric proof for the classical types. Finally, we show how the cases F4, E6 and E7 can be deduced from the E8-case.

In the last 20 years the formal approach to the development of software turned out to be a crucial technique for the generation of correct programs. This idea has its theoretical base into the several semi-automatic methods to transform a formal specification that describe the behavior of a program into an effective executable piece of code. One of this is the so-called "program extraction from proof". The idea is that from an constructive proof of a formula "for each x there exists y such that P(x,y)" we can automatically extract a program "t" such that the property P(x,t(x)) hold. In our days such proofs are normally written by ad-hoc tools (some of them are: COQ, ISABLLE, MINLOG, PX, AGDA, etc...) called "proof assistants". Even if today this technique is pretty well established, the "manipulation" of proofs in order to develop performing programs did not received big attention. In this thesis we will develop several automatic and semi-automatic methods in order to extract efficient code from constructive proofs. Our field of application will be computational biology, a research field in which the development of efficient programs is crucial. So our main goal will be to show how the manipulation of formal proofs, essentially studied by proof theorist, has a big effect also in practical program generation.

Die meisten internationalen und oft auch nationalen Netzverbindungen sind als horizontal gekoppelte Teildienste realisiert, die von mehreren Service Providern (SPs) erbracht werden. Die Ende-zu-Ende (E2E) Dienstgüte (engl. Quality of Service, QoS) setzt sich aus der Güte der involvierten Teildienste zusammen. In Bezug auf die E2E-QoS haben sich zwischen den SPs zwei Herangehensweisen etabliert: für die garantierte E2E-Dienstgüte werden üblicherweise hierarchische Organisationsbeziehungen aufgebaut, bei einer Gleichberechtigung der beteiligten Provider (was bei Internet- und Telefonverbindungen häufig der Fall ist) hat sich die sog. Best-Effort-Strategie durchgesetzt. Durch die Anforderungen der modernen internationalen Forschungsprojekte und der neuartigen kundenorientierten Dienste ist nun der Bedarf entstanden, die E2E-QoS bei Netzverbindungen auch dann zu garantieren, wenn der Aufbau hierarchischer Organisationsbeziehungen aus diversen Gründen nicht möglich ist. % Die Dienstklasse, die die angesprochenen technischen und organisatorischen Eigenschaften in sich vereint, wird in dieser Arbeit als Verkettete Dienste (engl.: Concatenated Services) referenziert. Um die Anforderungen für die zu entwickelnde Lösung zu bestimmen, werden in dieser Arbeit die Interessen unterschiedlicher Akteure in verschiedenen Verbindungsdiensten analysiert. Eine darauffolgende Untersuchung von existierenden Lösungen in relevanten Forschungsbereichen liefert eine Reihe von möglichen Lösungsbausteinen und lehrreichen Erfahrungen, die bei der Konzeption der eigentlichen Lösung berücksichtigt werden. Die entwickelte Lösung besteht aus drei Teilen. Der Kern der Lösung ist durch die SLM-aware Routing-Architektur gegeben. In der entwickelten Lösung werden während des Routings nicht nur der Pfadverlauf, sondern auch die QoS-Anforderungen und die benötigte Managementfunktionalität aller involvierten Teildienste bestimmt. Durch die Bestimmung der Akteure, die die benötigten Rollen übernehmen sollen, sowie der Kommunikationswege zwischen Managementkomponenten wird die Durchführung von Service-Level-Management (SLM) in allen Lebenszyklusphasen ermöglicht. Die Integrationsrolle zwischen den SPs wird von dem Kommunikationsprotokoll übernommen. Das Protokoll ist sowohl für die Signalisierung als auch für den Informationsaustausch während des kompletten Dienstinstanz-Lebenszyklus zuständig. Die mit den erlaubten Signalen assoziierten Basisprozesse erlauben eine unmissverständliche und intuitive Definition des erwarteten Verhaltens. Die Definition von Referenzprozessen für Service Level Management bei Verketteten Diensten rundet die entwickelte Lösung ab. Die SLM-Prozesse bauen ausschließlich auf dem zuvor definierten Kommunikationsprotokoll auf, wodurch eine leichte Anpassbarkeit dieser Prozesse an zusätzliche Anforderungen gewährleistet wird. Die Funktionsweise der entwickelten Lösung wird an einem detaillierten Beispiel illustriert. Die Güte der Lösung wird anhand der Erfahrungen mit der Integration der Lösungsteile in verschiedenen Forschungsprojekten sowie anhand der aufgestellten Anforderungen bewertet. Ein kurzer Ausblick auf die Weiterentwicklungsmöglichkeiten und auf verwandte Forschungsfragestellungen schließt diese Arbeit ab.

In prospective randomized trials differences in population based means can be considered as estimates of mean causal exposure or treatment effects. Nevertheless, occurence of intermediate events in the course of a trial may lead to biased estimates of treatment effects. Particularly this will be the case, if the probability of such an event is not independent of initial treatment allocation and the intermediate event is both a risk factor for the main outcome parameter (e.g. survival) and a predictor of subsequent treatment. This situation was referred as 'treatment by indication problem' by Robins (1992) and is common in epidemiological trials. Robins demonstrated that the usual approach of an adjusted estimation of treatment effect using a time-dependent proportional hazards model may be biased in this situation, whether or not one further adjusts for past confounder history in the analysis. In this thesis a novel inference procedure for randomized trials is introduced which is based on the idea of Robin's G-Estimation principle but particularly consideres specifics of randomized trials. The suggested procedure allows for an unbiased and consistent estimation of a treatment effect parameter (or paremeter vector) which is connected by a real-valued function to the parameters of an underlying distribution of survival times. In fulfilment of the requirements of a causal individual-level based model, a link of a subject's observed and counterfactual survival time is directly achieved by the inverse distribution function of survival times in a reference treatment arm. In this term, causal inference is feasible based on the likelihood function and its corresponding test statistics, even under appropriate consideration of time-dependent confounders.

In the 1990s a number of technological innovations appeared that revolutionized biology, and 'Bioinformatics' became a new scientific discipline. Microarrays can measure the abundance of tens of thousands of mRNA species, data on the complete genomic sequences of many different organisms are available, and other technologies make it possible to study various processes at the molecular level. In Bioinformatics and Biostatistics, current research and computations are limited by the available computer hardware. However, this problem can be solved using high-performance computing resources. There are several reasons for the increased focus on high-performance computing: larger data sets, increased computational requirements stemming from more sophisticated methodologies, and latest developments in computer chip production. The open-source programming language 'R' was developed to provide a powerful and extensible environment for statistical and graphical techniques. There are many good reasons for preferring R to other software or programming languages for scientific computations (in statistics and biology). However, the development of the R language was not aimed at providing a software for parallel or high-performance computing. Nonetheless, during the last decade, a great deal of research has been conducted on using parallel computing techniques with R. This PhD thesis demonstrates the usefulness of the R language and parallel computing for biological research. It introduces parallel computing with R, and reviews and evaluates existing techniques and R packages for parallel computing on Computer Clusters, on Multi-Core Systems, and in Grid Computing. From a computer-scientific point of view the packages were examined as to their reusability in biological applications, and some upgrades were proposed. Furthermore, parallel applications for next-generation sequence data and preprocessing of microarray data were developed. Microarray data are characterized by high levels of noise and bias. As these perturbations have to be removed, preprocessing of raw data has been a research topic of high priority over the past few years. A new Bioconductor package called affyPara for parallelized preprocessing of high-density oligonucleotide microarray data was developed and published. The partition of data can be performed on arrays using a block cyclic partition, and, as a result, parallelization of algorithms becomes directly possible. Existing statistical algorithms and data structures had to be adjusted and reformulated for the use in parallel computing. Using the new parallel infrastructure, normalization methods can be enhanced and new methods became available. The partition of data and distribution to several nodes or processors solves the main memory problem and accelerates the methods by up to the factor fifteen for 300 arrays or more. The final part of the thesis contains a huge cancer study analysing more than 7000 microarrays from a publicly available database, and estimating gene interaction networks. For this purpose, a new R package for microarray data management was developed, and various challenges regarding the analysis of this amount of data are discussed. The comparison of gene networks for different pathways and different cancer entities in the new amount of data partly confirms already established forms of gene interaction.

We consider two-player games of perfect information of length some cardinal $\kappa$. It is well-known that for $\kappa \geq \omega_1$ the full axiom of determinacy for these games fails, thus we investigate three weaker forms of it. We obtain the measurability of $\kappa^{+}$ under $DC_{\kappa}$-the axiom of dependent choices generalized to $\kappa$. We generalize the notions of perfect and meager sets and provide characterizations with some special kinds of games. We show that under an additional assumption one of our three axioms follows from the other two.

Im vorliegenden Band werden Erkenntnisse sowohl der psychologischen als auch der mathematikdidaktischen Forschung zusammengetragen. Eine eigene Untersuchung, die im Kern aus einer Interviewstudie besteht, ergänzt die Ergebnisse zum Wissen von Schülerinnen und Schülern zu den Begriffen der Analysis.

Die Bedeutung multimedialer Dienste hat in den letzten Jahren beträchtlich zugenommen. Ihre Nutzung ist heutzutage nicht mehr nur auf stationäre Geräte beschränkt: durch bessere mobile Endgeräte und leistungsfähigere Netze können diese Dienste immer mehr auch unterwegs eingesetzt werden. Gerade im mobilen Umfeld kämpfen sie aber mit zwei grundlegenden Problemen: zum einen ist es für den Nutzer schwierig, aus der riesigen Menge der Inhalte diejenigen zu finden, die für ihn wirklich relevant sind. Dieses Problem tritt auch bei stationärer Nutzung auf, die schlechteren Eingabemöglichkeiten und die geringere Bandbreite mobiler Endgeräte schränken aber gerade hier die Nutzung massiv ein. Zum anderen zeichnen sich mobile Geräte durch eine starke Heterogenität aus. Um multimediale Inhalte komfortabel nutzen zu können, muss deren optimale Darstellung für die unterschiedlichen Charakteristika dieser heterogenen Endgeräte gefunden werden. Eine Lösung für diese beiden Probleme ist die Personalisierung multimedialer Inhalte. Im mobilen Bereich findet die Nutzung multimedialer Inhalte in einem wesentlich dynamischeren Kontext statt. Der Nutzer kann sich räumlich bewegen, die Umgebungslautstärke und die Lichtverhältnisse ändern sich häufig, und er ist der Witterung ausgesetzt. Wie diese Informationen genutzt werden, um die Personalisierung multimedialer Inhalte zu unterstützen, soll im Rahmen dieser Arbeit näher untersucht werden. Dafür wurde die Multimedia Adaptation and Selection Language (MASL) zur Beschreibung von Inhalten und Nutzern entwickelt. Die Informationen, die mit dieser Sprache erfasst werden, werden durch Nutzereingabe (explizit) oder automatisch (implizit) gewonnen. Exemplarisch wird dies in der vorliegenden Arbeit mit der expliziten und impliziten Gewinnung von Schlüsselwörtern zu Inhalten und Nutzerbewertungen gezeigt. Die Beschreibungen in MASL werden verwendet, um multimediale Inhalte Kontext-abhängig auszuwählen und die gewählten Inhalte in der Darstellung an den aktuellen Nutzungskontext anzupassen. Für die Auswahl werden Empfehlungssysteme eingesetzt, die Inhalte gemäß den aktuellen Kontextinformationen des Nutzers selektieren. Die entwickelten Ansätze werden in ein einheitliches Framework integriert, das flexibel konfigurierbar ist. Für die Anpassung der Darstellung wird eine Middleware entwickelt, die verteilt arbeitet: der Server-seitige Teil führt eine Voranpassung der Inhalte durch, der Client beendet den Anpassungsprozess.

This dissertation describes an exploration of digital tabletop interaction styles, with the ultimate goal of informing the design of a new model for tabletop interaction. In the context of this thesis the term digital tabletop refers to an emerging class of devices that afford many novel ways of interaction with the digital. Allowing users to directly touch information presented on large, horizontal displays. Being a relatively young field, many developments are in flux; hardware and software change at a fast pace and many interesting alternative approaches are available at the same time. In our research we are especially interested in systems that are capable of sensing multiple contacts (e.g., fingers) and richer information such as the outline of whole hands or other physical objects. New sensor hardware enable new ways to interact with the digital. When embarking into the research for this thesis, the question which interaction styles could be appropriate for this new class of devices was a open question, with many equally promising answers. Many everyday activities rely on our hands ability to skillfully control and manipulate physical objects. We seek to open up different possibilities to exploit our manual dexterity and provide users with richer interaction possibilities. This could be achieved through the use of physical objects as input mediators or through virtual interfaces that behave in a more realistic fashion. In order to gain a better understanding of the underlying design space we choose an approach organized into two phases. First, two different prototypes, each representing a specific interaction style – namely gesture-based interaction and tangible interaction – have been implemented. The flexibility of use afforded by the interface and the level of physicality afforded by the interface elements are introduced as criteria for evaluation. Each approaches’ suitability to support the highly dynamic and often unstructured interactions typical for digital tabletops is analyzed based on these criteria. In a second stage the learnings from these initial explorations are applied to inform the design of a novel model for digital tabletop interaction. This model is based on the combination of rich multi-touch sensing and a three dimensional environment enriched by a gaming physics simulation. The proposed approach enables users to interact with the virtual through richer quantities such as collision and friction. Enabling a variety of fine-grained interactions using multiple fingers, whole hands and physical objects. Our model makes digital tabletop interaction even more “natural”. However, because the interaction – the sensed input and the displayed output – is still bound to the surface, there is a fundamental limitation in manipulating objects using the third dimension. To address this issue, we present a technique that allows users to – conceptually – pick objects off the surface and control their position in 3D. Our goal has been to define a technique that completes our model for on-surface interaction and allows for “as-direct-as possible” interactions. We also present two hardware prototypes capable of sensing the users’ interactions beyond the table’s surface. Finally, we present visual feedback mechanisms to give the users the sense that they are actually lifting the objects off the surface. This thesis contributes on various levels. We present several novel prototypes that we built and evaluated. We use these prototypes to systematically explore the design space of digital tabletop interaction. The flexibility of use afforded by the interaction style is introduced as criterion alongside the user interface elements’ physicality. Each approaches’ suitability to support the highly dynamic and often unstructured interactions typical for digital tabletops are analyzed. We present a new model for tabletop interaction that increases the fidelity of interaction possible in such settings. Finally, we extend this model so to enable as direct as possible interactions with 3D data, interacting from above the table’s surface.

Game theory is a branch of applied mathematics studying the interaction of self-interested entities, so-called agents. Its central objects of study are games, mathematical models of real-world interaction, and solution concepts that single out certain outcomes of a game that are meaningful in some way. The solutions thus produced can then be viewed both from a descriptive and from a normative perspective. The rise of the Internet as a computational platform where a substantial part of today's strategic interaction takes place has spurred additional interest in game theory as an analytical tool, and has brought it to the attention of a wider audience in computer science. An important aspect of real-world decision-making, and one that has received only little attention in the early days of game theory, is that agents may be subject to resource constraints. The young field of algorithmic game theory has set out to address this shortcoming using techniques from computer science, and in particular from computational complexity theory. One of the defining problems of algorithmic game theory concerns the computation of solution concepts. Finding a Nash equilibrium, for example, i.e., an outcome where no single agent can gain by changing his strategy, was considered one of the most important problems on the boundary of P, the complexity class commonly associated with efficient computation, until it was recently shown complete for the class PPAD. This rather negative result for general games has not settled the question, however, but immediately raises several new ones: First, can Nash equilibria be approximated, i.e., is it possible to efficiently find a solution such that the potential gain from a unilateral deviation is small? Second, are there interesting classes of games that do allow for an exact solution to be computed efficiently? Third, are there alternative solution concepts that are computationally tractable, and how does the value of solutions selected by these concepts compare to those selected by established solution concepts? The work reported in this thesis is part of the effort to answer the latter two questions. We study the complexity of well-known solution concepts, like Nash equilibrium and iterated dominance, in various classes of games that are both natural and practically relevant: ranking games, where outcomes are rankings of the players; anonymous games, where players do not distinguish between the other players in the game; and graphical games, where the well-being of any particular player depends only on the actions of a small group other players. In ranking games, we further compare the payoffs obtainable in Nash equilibrium outcomes with those of alternative solution concepts that are easy to compute. We finally study, in general games, solution concepts that try to remedy some of the shortcomings associated with Nash equilibrium, like the need for randomization to achieve a stable outcome.

Die steigende Komplexität von IT-Diensten führt zu neuen Herausforderungen im IT-Service-Management(ITSM). Aufgrund von neuartigen SourcingModellen, Trends wie eBusiness oder auch regulatorischen Vorgaben wächst zunehmend die Notwendigkeit, aber auch die Gelegenheit für eine partnerschaftliche Kollaboration zwischen IT Providern. Jenseits des hierarchischen Modells in der Zusammenarbeit von IT Providern, bei dem ein fokaler Provider eine Reihe von weiteren Dienstleistern mit der Erbringung von Basisdiensten beauftragt, gewinnen alternative Formen der Kooperation an Bedeutung. Die Gewährleistung einer definierten Ende-zu-Ende Dienstqualität ist dabei eine der wichtigsten Herausforderungen. Die Zusammenarbeit von IT Providern erfordert die Spezifikation von interorganisationalen Betriebsprozessen. Die etablierten ITSM Frameworks adressieren jedoch alternative Formen der Diensterbringung nicht; so bleiben kooperierende IT Provider bei der Definition von interorganisationalen ITSMProzessen als Basis ihrer Zusammenarbeit weitgehend auf sich alleine gestellt. Um auf die spezifischen Herausforderungen von Szenarien eingehen zu können, die von den etablierten ITSM Frameworks nicht abgedeckt werden, fokussiert diese Arbeit auf die Dienstklasse der Verketteten Dienste, das sind providerübergreifende, horizontale Dienstketten auf der gleichen funktionalen Schicht. Im Unterschied zu klassischen Szenarien der kooperativen Erbringung von ITDiensten, wie z.B. IP Peering im Internet, wird für Verkettete Dienste eine definierte Dienstqualität und ein serviceorientiertes Management gefordert. Der erste Teil der Arbeit leistet auf der Basis einer Untersuchung realer Szenarien eine eingehende Analyse der ManagementHerausforderungen und der spezifischen Anforderungen für die Prozessdefinition Verketteter Dienste. Zur Kategorisierung der vielfältigen Formen der Zusammenarbeit von Providern wird ein Raster von Koordinationsmustern definiert. Die Betrachtung des Status Quo zeigt, dass, obwohl eine Reihe von Vorarbeiten in den Disziplinen des IT-Service-Managements sowie der Informations- und Prozessmodellierung vorliegt, die Anwendung von universellen Modellierungssprachen auf interorganisationale ITSMProzesse derzeit kaum abgedeckt wird. Im Hauptteil der Arbeit wird dazu die neue Methode ITSMCooP (ITSM Processes for Cooperating Providers) eingeführt. Aufbauend auf der Prozessmodellierungssprache BPMN und dem Shared Information/Data Model (SDI) des TeleManagement-Forums, besteht die Methode aus einer Sammlung von Modellierungskonventionen und Empfehlungen, die alle relevanten Aspekte der Modellierung von interorganisationalen Prozessen abdecken. Die Erstellung von Informations- und Prozessmodellen wird geleitet von einer Vorgehensweise zur Prozessdefinition, die sowohl Referenzprozesse der ITSM Frameworks als auch die spezifischen Koordinationsmuster Verketteter Dienste berücksichtigt. Die Arbeit wird abgerundet durch die Anwendung der Methode ITSMCooP auf ein reales, komplexes Szenario.

In this thesis, a novel sequential genes selection and classification (k-SS) method is proposed. The method is analogous to the classical non-linear stepwise variable selection (SVS) methods but unlike any of the SVS methods, this new method uses the misclassification error rates (MERs) as its search criteria for informative marker genes in any given microarray data. Here, the importance of any selected gene is determined based on its marginal contribution at improving the prediction accuracy of the classification rule. This method ensures continuous selection of more genes in as much as the improvements brought into the decision models by the selected genes are considered to be significant enough by some established test criteria. However, further gene selection terminates when none of the remaining genes is capable at improving the prediction accuracy (lowering the MER) of the current model. Therefore, our approach only seeks to select the best combination of k marker genes that are most predictive of the biological samples in any given microarray data sets. An important feature of our new k-SS method is that the size α used by its test is not arbitrarily fixed by the user as common to some of the classical SVS methods. Rather, the value of α at which the best prediction accuracy is achieved (or the best combination of genes is selected) is determined by cross-validation. The new k-SS classifier competes favourably with selected eight existing classification methods using eleven published microarray data sets. The k-SS classifier is very simple to apply and does not require any rigid assumption for its implementation. Another merit of this method lies in its ability to select only those genes that are of biological relevance to the existing cancer sub-groups in microarray data sets. Lastly, we proposed a new preliminary feature selection procedure that employs the cross-validated area under the ROC curve (CVAUC) for gene selection. This method is capable at removing all the irrelevant genes at the preliminary selection stage before any standard classifier like the k-SS method is employed on the remaining data set for final optimum gene selection and classification of mRNA samples. Unlike some other data pruning methods, the new method employs the sub-sampling technique of the v-fold cross-validation to ensure consistency and efficiency of selections made at the preliminary selection stage.

In this thesis, hierarchical graphs are investigated from two different angles – as a general modelling principle for (geo)spatial networks and as a practical means to enhance navigation in buildings. The topics addressed are of interest from a multi-disciplinary point of view, ranging from Computer Science in general over Artificial Intelligence and Computational Geometry in particular to other fields such as Geographic Information Science. Some hierarchical graph models have been previously proposed by the research community, e.g. to cope with the massive size of road networks, or as a conceptual model for human wayfinding. However, there has not yet been a comprehensive, systematic approach for modelling spatial networks with hierarchical graphs. One particular problem is the gap between conceptual models and models which can be readily used in practice. Geospatial data is commonly modelled - if at all - only as a flat graph. Therefore, from a practical point of view, it is important to address the automatic construction of a graph hierarchy based on the predominant data models. The work presented deals with this problem: an automated method for construction is introduced and explained. A particular contribution of my thesis is the proposition to use hierarchical graphs as the basis for an extensible, flexible architecture for modelling various (geo)spatial networks. The proposed approach complements classical graph models very well in the sense that their expressiveness is extended: various graphs originating from different sources can be integrated into a comprehensive, multi-level model. This more sophisticated kind of architecture allows for extending navigation services beyond the borders of one single spatial network to a collection of heterogeneous networks, thus establishing a meta-navigation service. Another point of discussion is the impact of the hierarchy and distribution on graph algorithms. They have to be adapted to properly operate on multi-level hierarchies. By investigating indoor navigation problems in particular, the guiding principles are demonstrated for modelling networks at multiple levels of detail. Complex environments like large public buildings are ideally suited to demonstrate the versatile use of hierarchical graphs and thus to highlight the benefits of the hierarchical approach. Starting from a collection of floor plans, I have developed a systematic method for constructing a multi-level graph hierarchy. The nature of indoor environments, especially their inherent diversity, poses an additional challenge: among others, one must deal with complex, irregular, and/or three-dimensional features. The proposed method is also motivated by practical considerations, such as not only finding shortest/fastest paths across rooms and floors, but also by providing descriptions for these paths which are easily understood by people. Beyond this, two novel aspects of using a hierarchy are discussed: one as an informed heuristic exploiting the specific characteristics of indoor environments in order to enhance classical, general-purpose graph search techniques. At the same time, as a convenient by- product of this method, clusters such as sections and wings can be detected. The other reason is to better deal with irregular, complex-shaped regions in a way that instructions can also be provided for these spaces. Previous approaches have not considered this problem. In summary, the main results of this work are: • hierarchical graphs are introduced as a general spatial data infrastructure. In particular, this architecture allows us to integrate different spatial networks originating from different sources. A small but useful set of operations is proposed for integrating these networks. In order to work in a hierarchical model, classical graph algorithms are generalised. This finding also has implications on the possible integration of separate navigation services and systems; • a novel set of core data structures and algorithms have been devised for modelling indoor environments. They cater to the unique characteristics of these environments and can be specifically used to provide enhanced navigation in buildings. Tested on models of several real buildings from our university, some preliminary but promising results were gained from a prototypical implementation and its application on the models.