No description available.

No description available.

A datacenter hosts hundreds of thousands of servers and a huge amount of bandwidth is required to accommodate communication between thousands of servers. Several packet switched based datacenter architectures are proposed to cater the high bandwidth requirement using multilayer network topologies, however at the cost of increased network complexity and high power consumption. In recent years, the focus has shifted from packet switching to optical circuit switching to build the data center networks as it can support on demand connectivity and high bit rates with low power consumption. On the other hand, with the advent of Software Defined Networking (SDN) and Network Function Virtualization (NFV), the role of datacenters has become more crucial. It has increased the need of dynamicity and flexibility within a datacenter adding more complexity to datacenter networking. With NFV, service chaining can be achieved in a datacenter where virtualized network functions (VNFs) running on commodity servers in a datacenter are instantiated/terminated dynamically. A datacenter also needs to cater large capacity requirement as service chaining involves steering of large aggregated flows. Use of optical circuit switching in data center networks is quite promising to meet such dynamic and high capacity traffic requirements. In this thesis work, a novel and modular optical data center network (DCN) architecture that uses multi-directional wavelength switches (MD-WSS) is introduced. VNF service chaining use case is considered for evaluation of this DCN and the end-to-end service chaining problem is formulated as three inter-connected sub-problems: multiplexing of VNF service chains, VNFs placement in the datacenter and routing and wavelength assignment. This thesis presents integer linear programming (ILP) formulation and heuristics for solving these problems, and numerically evaluate them. / Ett datacenter inrymmer hundratusentals servrar och en stor mängd bandbredd krävs för att skicka data mellan tusentals servrar. Flera datacenter baserade på paketförmedlande arkitekturer föreslås för att tillgodose kravet på hög bandbredd med hjälp av flerskiktsnätverkstopologier, men på bekostnad av ökad komplexitet i nätverken och hög energiförbrukning. Under de senaste åren har fokus skiftat från paketförmedling till optisk kretsomkoppling for att bygga datacenternätverk som kan stödja på-begäran-anslutningar och höga bithastigheter med låg strömförbrukning. Å andra sidan, med tillkomsten av Software Defined Networking (SDN) och nätverksfunktionen Virtualisering (NFV), har betydelsen av datacenter blivit mer avgörande. Det har ökat behovet av dynamik och flexibilitet inom ett datacenter, vilket leder till storre komplexitet i datacenternätverken. Med NFV kan tjänstekedjor åstadkommas i ett datacenter, där virtualiserade nätverksfunktioner (VNFs) som körs på servrar i ett datacenter kan instansieras och avslutas dynamiskt. Ett datacenter måste också tillgodose kravet på stor kapacitet eftersom tjänstekedjan innebär styrning av stora aggregerade flöden. Användningen av optisk kretsomkoppling i datacenternätverk ser ganska lovande ut for att uppfylla sådana trafikkrav dynamik och hög kapacitet. I detta examensarbete, har en ny och modulär optisk datacenternätverksarkitektur (DCN) som använder flerriktningvåglängdsswitchar (MD-WSS) införs. Ett användningsfall av VNF-tjänstekedjor noga övervägd för utvärdering av denna DCN och end-to-end-servicekedjans problem formuleras som tre sammankopplade delproblem: multiplexering av VNF-servicekedjor, VNF placering i datacentret och routing och våglängd uppdrag. Denna avhandling presenterar heltalsprogrammering (ILP) formulering och heuristik för att lösa dessa problem och numeriskt utvärdera dem.

O trabalho tem por principal objetivo verificar, preliminarmente, a possibilidade de reduzir a quantidade de indivíduos na amostra de Pesquisa de Entrevistas Domiciliares, sem prejudicar a qualidade e representatividade da mesma. Analisar a influência das características espaciais e de uso de solo da área urbana constitui o objetivo intermediário. Para ambos os objetivos, a principal ferramenta utilizada foi o minerador de dados denominado Árvore de Decisão e Classificação contido no software S-Plus 6.1, que encontra as relações entre as características socioeconômicas dos indivíduos, as características espaciais e de uso de solo da área urbana e os padrões de viagens encadeadas. Os padrões de viagens foram codificados em termos de sequência cronológica de: motivos, modos, durações de viagem e períodos do dia em que as viagens ocorrem. As análises foram baseadas nos dados da Pesquisa de Entrevistas Domiciliares realizada pela Agência de Cooperação Internacional do Japão e Governo do Estado do Pará em 2000 na Região Metropolitana de Belém. Para se atingir o objetivo intermediário o método consistiu em analisar, através da Árvore de Decisão e Classificação, a influência da variável categórica Macrozona, que representa as características espaciais e de uso de solo da área urbana, nos padrões de viagens encadeadas realizados pelos indivíduos. Para o objetivo principal, o método consistiu em escolher, aleatoriamente, sub-amostras contendo 25% de pessoas da amostra final e verificar, através do Processamento de Árvores de Decisão e Classificação e do teste estatístico Kolmogorov - Smirnov, se os modelos obtidos a partir das amostras reduzidas conseguem ilustrar bem a freqüência de ocorrência dos padrões de viagens das pessoas da amostra final. Concluiu-se que as características espaciais e de uso de solo influenciam os padrões de encadeamento de viagens, e portanto foram incluídas como variáveis preditoras também nos modelos obtidos a partir das sub-amostras. A conclusão principal foi a não rejeição da hipótese de que é possível reduzir o tamanho da amostra de pesquisas domiciliares para fins de estudo do encadeamento de viagens. Entretanto ainda são necessárias muitas outras verificações antes de aceitar esta conclusão. / The main aim of this work is to verify, the possibility of reducing the sample size in home-interview surveys, without being detrimental to the quality and representation. The sub aim of this work is to analyze the influence of spatial characteristics and land use of an urban area. For both aims, the main analyses tool used was Data Miner called the Decision and Classification Tree which is in the software S-Plus 6.1. The Data Miner finds relations between trip chaining patterns and individual socioeconomic characteristics, spatial characteristics and land use patterns. The trip chaining patterns were coded in terms of chronological sequence of trip purpose, travel mode, travel time and the period of day in which travel occurs. The analyses were based on home-interview surveys carried out in the Belém Metropolitan Area in 2000, by Japan International Cooperation Agency and Pará State Government. In order to achieve the sub aim of this work, the method consisted of analyzing, using the Decision and Classification Tree, the influence of the categorical variable \"Macrozona\", which represents spatial characteristics and urban land use patterns, in trip chaining patterns carried by the individuals. Concerning the main aim, the method consisted of choosing sub-samples randomly containing 25% of the final sample of individuals and verifying (using Decision and Classification Tree and Kolmogorov-Smirnov statistical test) whether the models obtained from the reduced samples can describe the frequency of the occurrence of the individuals trip chaining patterns in the final sample well. The first conclusion is that spatial characteristics and land use of the urban area have influenced the trip chaining patterns, and therefore they were also included as independent variables in the models obtained from the sub-samples. The main conclusion was the non-rejection of the hypothesis that it is possible to reduce the sample size in home-interview surveys used for trip-chaining research. Nevertheless, several other verifications are necessary before accepting this conclusion.

O objetivo deste trabalho foi desenvolver um modelo para reconhecer e reproduzir padrões de viagens encadeadas a pé. O processo de modelagem foi conduzido através da aplicação das técnicas das Redes Neurais Artificiais (RNAs), utilizando-se de uma rede estática MLP e de rede dinâmica Elman. A análise do desempenho do modelo foi baseada nos dados de uma pesquisa de Origem-Destino realizada, em 1987, pelo METRÔ-SP na Região Metropolitana de São Paulo. Na modelagem foi fixado o modo de viagem a pé, e, na abordagem seqüencial, padrões de viagens individuais foram representados em termos de dois componentes: duração da viagem e tipo de atividades. A análise foi realizada partindo da classificação geral e específica para cada segmento do encadeamento de viagens, o que permitiu a comparação dos resultados entre padrões de viagens observados e os reproduzidos pelas redes. Na classificação geral, cinco dos padrões previstos com maior freqüência pelas RNAs representaram em média 58,9% dos indivíduos no conjunto de dados usado para testar o desempenho do modelo. Para o vetor de duas e quatro viagens, as redes neurais reproduziram 50% das durações de viagem e 90% das atividades, tais como Trabalho e Escola. Embora esses resultados não pareçam muito robustos, não significa que eles estejam errados. As porcentagens acima representam a probabilidade de uma pessoa realizar viagens com aquelas durações ou tipo de atividades. / The main objective of this work was to develop a model for recognizing and reproduzing trip-chaining patterns by walk. The process of modeling was conducted applying the techniques of Artificial Neural Networks (ANNs), by using one of the static networks MLP and the Elman dynamic network. The analysis of the performance of the model was based on the origin-destination home-interview survey carried out by METRÔ-SP in São Paulo Metropolitan Area in 1987. The mode of trip by walk was fixed in the model, and, in the sequential approach, individual travel patterns were represented in terms of two components: trip duration and activity type. The analysis was accomplished starting from the general and specific classifications for each segment of the chained trips, which allowed the comparison of the results between the observed travel patterns and reproduced ones through ANNs. In general classification, 5 of the patterns most frequently predicted by the ANNs represented 58.9% of the individuals in the dataset used for testing the model performance. For the vectors of two and four trips, the neural networks reproduced 50% of trip durations and 90% of the activities, such as work and school. Although those results seem not so robust, it does not mean that they are wrong. The percentages above represent the probability of a person making trips with those durations or type of activities.

O objetivo deste trabalho foi desenvolver um modelo para reconhecer e reproduzir padrões de viagens encadeadas a pé. O processo de modelagem foi conduzido através da aplicação das técnicas das Redes Neurais Artificiais (RNAs), utilizando-se de uma rede estática MLP e de rede dinâmica Elman. A análise do desempenho do modelo foi baseada nos dados de uma pesquisa de Origem-Destino realizada, em 1987, pelo METRÔ-SP na Região Metropolitana de São Paulo. Na modelagem foi fixado o modo de viagem a pé, e, na abordagem seqüencial, padrões de viagens individuais foram representados em termos de dois componentes: duração da viagem e tipo de atividades. A análise foi realizada partindo da classificação geral e específica para cada segmento do encadeamento de viagens, o que permitiu a comparação dos resultados entre padrões de viagens observados e os reproduzidos pelas redes. Na classificação geral, cinco dos padrões previstos com maior freqüência pelas RNAs representaram em média 58,9% dos indivíduos no conjunto de dados usado para testar o desempenho do modelo. Para o vetor de duas e quatro viagens, as redes neurais reproduziram 50% das durações de viagem e 90% das atividades, tais como Trabalho e Escola. Embora esses resultados não pareçam muito robustos, não significa que eles estejam errados. As porcentagens acima representam a probabilidade de uma pessoa realizar viagens com aquelas durações ou tipo de atividades. / The main objective of this work was to develop a model for recognizing and reproduzing trip-chaining patterns by walk. The process of modeling was conducted applying the techniques of Artificial Neural Networks (ANNs), by using one of the static networks MLP and the Elman dynamic network. The analysis of the performance of the model was based on the origin-destination home-interview survey carried out by METRÔ-SP in São Paulo Metropolitan Area in 1987. The mode of trip by walk was fixed in the model, and, in the sequential approach, individual travel patterns were represented in terms of two components: trip duration and activity type. The analysis was accomplished starting from the general and specific classifications for each segment of the chained trips, which allowed the comparison of the results between the observed travel patterns and reproduced ones through ANNs. In general classification, 5 of the patterns most frequently predicted by the ANNs represented 58.9% of the individuals in the dataset used for testing the model performance. For the vectors of two and four trips, the neural networks reproduced 50% of trip durations and 90% of the activities, such as work and school. Although those results seem not so robust, it does not mean that they are wrong. The percentages above represent the probability of a person making trips with those durations or type of activities.

O trabalho tem por principal objetivo verificar, preliminarmente, a possibilidade de reduzir a quantidade de indivíduos na amostra de Pesquisa de Entrevistas Domiciliares, sem prejudicar a qualidade e representatividade da mesma. Analisar a influência das características espaciais e de uso de solo da área urbana constitui o objetivo intermediário. Para ambos os objetivos, a principal ferramenta utilizada foi o minerador de dados denominado Árvore de Decisão e Classificação contido no software S-Plus 6.1, que encontra as relações entre as características socioeconômicas dos indivíduos, as características espaciais e de uso de solo da área urbana e os padrões de viagens encadeadas. Os padrões de viagens foram codificados em termos de sequência cronológica de: motivos, modos, durações de viagem e períodos do dia em que as viagens ocorrem. As análises foram baseadas nos dados da Pesquisa de Entrevistas Domiciliares realizada pela Agência de Cooperação Internacional do Japão e Governo do Estado do Pará em 2000 na Região Metropolitana de Belém. Para se atingir o objetivo intermediário o método consistiu em analisar, através da Árvore de Decisão e Classificação, a influência da variável categórica Macrozona, que representa as características espaciais e de uso de solo da área urbana, nos padrões de viagens encadeadas realizados pelos indivíduos. Para o objetivo principal, o método consistiu em escolher, aleatoriamente, sub-amostras contendo 25% de pessoas da amostra final e verificar, através do Processamento de Árvores de Decisão e Classificação e do teste estatístico Kolmogorov - Smirnov, se os modelos obtidos a partir das amostras reduzidas conseguem ilustrar bem a freqüência de ocorrência dos padrões de viagens das pessoas da amostra final. Concluiu-se que as características espaciais e de uso de solo influenciam os padrões de encadeamento de viagens, e portanto foram incluídas como variáveis preditoras também nos modelos obtidos a partir das sub-amostras. A conclusão principal foi a não rejeição da hipótese de que é possível reduzir o tamanho da amostra de pesquisas domiciliares para fins de estudo do encadeamento de viagens. Entretanto ainda são necessárias muitas outras verificações antes de aceitar esta conclusão. / The main aim of this work is to verify, the possibility of reducing the sample size in home-interview surveys, without being detrimental to the quality and representation. The sub aim of this work is to analyze the influence of spatial characteristics and land use of an urban area. For both aims, the main analyses tool used was Data Miner called the Decision and Classification Tree which is in the software S-Plus 6.1. The Data Miner finds relations between trip chaining patterns and individual socioeconomic characteristics, spatial characteristics and land use patterns. The trip chaining patterns were coded in terms of chronological sequence of trip purpose, travel mode, travel time and the period of day in which travel occurs. The analyses were based on home-interview surveys carried out in the Belém Metropolitan Area in 2000, by Japan International Cooperation Agency and Pará State Government. In order to achieve the sub aim of this work, the method consisted of analyzing, using the Decision and Classification Tree, the influence of the categorical variable \"Macrozona\", which represents spatial characteristics and urban land use patterns, in trip chaining patterns carried by the individuals. Concerning the main aim, the method consisted of choosing sub-samples randomly containing 25% of the final sample of individuals and verifying (using Decision and Classification Tree and Kolmogorov-Smirnov statistical test) whether the models obtained from the reduced samples can describe the frequency of the occurrence of the individuals trip chaining patterns in the final sample well. The first conclusion is that spatial characteristics and land use of the urban area have influenced the trip chaining patterns, and therefore they were also included as independent variables in the models obtained from the sub-samples. The main conclusion was the non-rejection of the hypothesis that it is possible to reduce the sample size in home-interview surveys used for trip-chaining research. Nevertheless, several other verifications are necessary before accepting this conclusion.

La quantité croissante de données générées est à l’origine de nombreuses problématiques en bioinformatique telles que le développement de nouvelles méthodes de traitement et d’analyse efficaces de ces données. Plus particulièrement, les réseaux de régulation des fonctions cellulaires sont au coeur de nombreux projets aujourd’hui. Il est donc nécessaire, afin d’appréhender correctement ces systèmes de régulation, de comprendre l’origine et de caractériser les acteurs de ces systèmes tels que les ARN et les pseudogènes.Nous avons établi une nouvelle méthode de comparaison d’une séquence ARN requête avec un jeu de séquences ARN cibles. Notre méthode se base sur (i) l’indexation préalable des graines en séquence/structure des ARN du jeu cible, (ii) la recherche des ARN cibles par détection des graines de la séquence requête présentes également dans le jeu de données cible et le chainage de ces graines, puis (iii) la complétion de l’alignement obtenu à l’aide d’un algorithme d’alignement exact incorporant des contraintes d’alignement. Cette méthode a été appliquée sur le jeu de données de BraliBase2.1. L’exactitude des résultats obtenus et l’efficacité de la méthode ont alors été comparés à la méthode d’alignement exact LocARNA et à son filtre basé sur un algorithme de chainage de graines récemment développé, ExpLocP. Notre méthode RNA-unchained permet d’améliorer significativement les temps de calcul de LocARNA et présente des temps de calcul similaires à ExpLocP, tout en améliorant l’exactitude des alignements finaux.De plus, nous avons développé une méthode, PseudOE, de détection et de caractérisation du pseudome au sein d’un génome et d’analyse comparative de ce pseudome entre plusieurs génomes. Cette méthode a ainsi permis de réaliser l’analyse du panpseudome de deux souches relativement distantes de l’espèce Oenococcus oeni et qui présentent des propriétés oenologiques opposées. On observe dans ces génomes compacts, de 1,8Mb, 8,5% de pseudogènes. Par comparaison aux autres génomes bactériens, les génomes d’O. oeni semblent sensibles à la pseudogénisation. La majorité des pseudogènes détectés ont pour origine des mutations de leur séquence et sont présents uniquement dans l’un des génomes, ce qui soutient l’hypothèse d’une origine récente de ces séquences et qui illustre la tendance des O. oeni à l’hypermutabilité. De plus, l’analyse des données fournies par PseudOE a permis la mise en évidence d’une organisation spatiale des pseudogènes au sein de territoires spécifiques du chromosome. L’ensemble de ces analyses illustre les particularités des pseudogènes chez O. oeni et apporte des informations supplémentaires concernant l’évolution des gènes/génomes dont les annotations de génomes pourraient retirer des bénéfices. / The increasing amount of available data is a source of many issues in bioinformatics such that the development of new methods of treatments and efficient analysis of data. Especially, regulatory networks are at the heart of many projects. Also, in order to understand regulatory systems, it appears to be necessary to characterize and to understand actors of these systems such as RNA and pseudogenes. We develop a new method to compare a query RNA with a static set of target RNAs. Our method is based on (i) a preliminary indexing of the sequence/structure seeds of the target RNAs, (ii) searching the potentially homolog RNAs by detecting seeds of the query present in targets, chaining these seeds, then (iii) completing the alignment using an anchor-based exact alignment algorithm. We apply our method on the benchmark Bralibase2.1. We compare our method accuracy and efficiency with the exact method LocARNA and its recent seeds-based speed-up ExpLocP. Our pipeline RNA-unchained greatly improves computation time of LocARNA and is comparable to the one of ExpLocP, while improving the overall accuracy of the final alignments.Moreover, we develop a new method, PseudOE, to detect and to characterize the pseudome of one genome, and to analyse by comparison two genomes at least. This method allows to analyse the pan-pseudome of two distantly related Oenococcus oeni strains with opposite oenological properties. Quite interestingly, with 8.5% of pseudogenes for a compact 1.8Mb genome, O. oeni appeared to be prone to pseudogenization compared to other bacteria. A great proportion of pseudogenes were found to come from mutational degradation suggesting a relatively recent origin that could illustrate the natural propensity of O. oeni for hypermutability. In addition, we identify a spatial organization of pseudogenes into dedicated chromosomal territories. These analysis illustrate peculiar properties of O. oeni pseudogenes, providing additional insights of gene/genome evolution from which future genome annotation will benefit.

OpenStreetMap (OSM) konnte sich seit der Gründung 2004 sehr schnell etablieren und stellt mittlerweile eine konkrete Alternative gegenüber vergleichbaren kommerziellen Anwendungen dar. Dieser Erfolg ist eindeutig auf das revolutionäre Grundkonzept des Projektes zurückzuführen. Weltweit werden räumliche Daten durch Mitglieder erhoben und dem Projekt OSM zur Verfügung gestellt. Über die zugrunde liegenden Lizenzbestimmungen wird sichergestellt, dass OSM-Daten frei verfügbar und kostenfrei weiter verwendbar sind. Vor allem die Vorstellung der Unabhängigkeit von proprietären Daten hat zu starker, weiterhin zunehmender globaler Beteiligung geführt. Resultierend daraus erreichen die verfügbaren Daten inzwischen hohe Dichte sowie Genauigkeit. Visualisierungen in Form von interaktiven, frei skalierbaren Weltkarten, welche über die vollständig automatisierten Softwarelösungen Mapnik und Osmarender erstellt werden, sind am weitesten verbreitet. Infolgedessen müssen kartographische Grundsätze und Regeln formalisiert und implementiert werden. Insbesondere in Bezug auf kartographische Generalisierung treten teils erhebliche Mängel in den entsprechenden Umsetzungen auf. Dies bildet den Ausgangspunkt der Untersuchung. Ausgehend von einer Ist-Analyse werden vorhandene Defizite identifiziert und anschließend Möglichkeiten zur Integration von Generalisierungsfunktionalitäten untersucht. Aktuelle Entwicklungen streben die Anwendung interoperabler Systeme im Kontext kartographischer Generalisierung an, mit dem Ziel Generalisierungsfunktionalitäten über das Internet bereitzustellen. Grundlage hierfür bilden die vom Open Geospatial Consortium (OGC) spezifizierten Web Processing Services (WPS). Sie ermöglichen die Analyse und Verarbeitung räumlicher Daten. In diesem Zusammenhang werden Web Generalization Services (WebGen-WPS) auf mögliche Integration in die Softwarelösungen untersucht und bilden somit einen zentralen Untersuchungsgegenstand der vorliegenden Arbeit. Mapnik stellt, nicht zuletzt durch dessen offengelegten Quelltext („Open Source“), optimale Voraussetzungen für jene Implementierungen zur Verfügung. Zur Verarbeitung von OSM-Daten verwendet Mapnik die freie Geodatenbank PostGIS, welche ebenfalls Funktionalitäten zur Analyse und Verarbeitung räumlicher Daten liefert. In diesem Kontext wird zusätzlich untersucht, inwiefern PostGIS-Funktionen Potential zur Anwendung kartographischer Generalisierung aufweisen. / OpenStreetMap (OSM) has established very quickly since its founding in 2004 and has become a suitable alternative to similar commercial applications. This success is clearly due to the revolutionary concept of the project. Spatial data is collected by members world-wide and is provided to the project OSM. The underlying license aggreement ensures that OSM-Data is freely available and can be used free of charge. Primarily, the idea of independence from proprietary data has led to strong, still growing, global participation. Resulting from that, the available data is now achieving high density and accuracy. Visualizations in form of interactive, freely scalable maps of the world, which are constructed by the fully automated software solutions Mapnik and Osmarender are most common. In consequence cartographic principles and rules must be formalized and implemented. Particularly with respect to cartographic generalization, some serious faults appear in the corresponding implementations. This is the starting point of this diploma thesis. Based on an analysis of the current state, actual existing deficiencies are identified and then examined for possibilities to integrate generalization functionalities. Recent developments aim at the deployment of interoperable systems in the context of cartographic generalization, with the intention of providing generalization functionalities over the Internet. This is based on Web Processing Services (WPS) that where developed by the Open Geospatial Consortium (OGC). They enable the analysis and processing of spatial data. In this context, Web Generalization Services (Webgen-WPS) are examined for possible integration into the software solutions and represent therefore a central object of investigation within that examination. Mapnik provides, not least through its “open source” code, ideal conditions for those implementations. Mapnik uses the “open source” spatial database PostGIS for the processing of OSM-Data, which also provides capabilities to analyze and process spatial data. In this context is examined in addition, to what extent the features have potential for implementation of cartographic generalization.

OpenStreetMap (OSM) konnte sich seit der Gründung 2004 sehr schnell etablieren und stellt mittlerweile eine konkrete Alternative gegenüber vergleichbaren kommerziellen Anwendungen dar. Dieser Erfolg ist eindeutig auf das revolutionäre Grundkonzept des Projektes zurückzuführen. Weltweit werden räumliche Daten durch Mitglieder erhoben und dem Projekt OSM zur Verfügung gestellt. Über die zugrunde liegenden Lizenzbestimmungen wird sichergestellt, dass OSM-Daten frei verfügbar und kostenfrei weiter verwendbar sind. Vor allem die Vorstellung der Unabhängigkeit von proprietären Daten hat zu starker, weiterhin zunehmender globaler Beteiligung geführt. Resultierend daraus erreichen die verfügbaren Daten inzwischen hohe Dichte sowie Genauigkeit. Visualisierungen in Form von interaktiven, frei skalierbaren Weltkarten, welche über die vollständig automatisierten Softwarelösungen Mapnik und Osmarender erstellt werden, sind am weitesten verbreitet. Infolgedessen müssen kartographische Grundsätze und Regeln formalisiert und implementiert werden. Insbesondere in Bezug auf kartographische Generalisierung treten teils erhebliche Mängel in den entsprechenden Umsetzungen auf. Dies bildet den Ausgangspunkt der Untersuchung. Ausgehend von einer Ist-Analyse werden vorhandene Defizite identifiziert und anschließend Möglichkeiten zur Integration von Generalisierungsfunktionalitäten untersucht. Aktuelle Entwicklungen streben die Anwendung interoperabler Systeme im Kontext kartographischer Generalisierung an, mit dem Ziel Generalisierungsfunktionalitäten über das Internet bereitzustellen. Grundlage hierfür bilden die vom Open Geospatial Consortium (OGC) spezifizierten Web Processing Services (WPS). Sie ermöglichen die Analyse und Verarbeitung räumlicher Daten. In diesem Zusammenhang werden Web Generalization Services (WebGen-WPS) auf mögliche Integration in die Softwarelösungen untersucht und bilden somit einen zentralen Untersuchungsgegenstand der vorliegenden Arbeit. Mapnik stellt, nicht zuletzt durch dessen offengelegten Quelltext („Open Source“), optimale Voraussetzungen für jene Implementierungen zur Verfügung. Zur Verarbeitung von OSM-Daten verwendet Mapnik die freie Geodatenbank PostGIS, welche ebenfalls Funktionalitäten zur Analyse und Verarbeitung räumlicher Daten liefert. In diesem Kontext wird zusätzlich untersucht, inwiefern PostGIS-Funktionen Potential zur Anwendung kartographischer Generalisierung aufweisen.:Inhaltsverzeichnis Aufgabenstellung ii Zusammenfassung iii Abstract iv Abbildungsverzeichnis viii Tabellenverzeichnis ix Abkürzungsverzeichnis x 1 Einleitung 1 1.1 Motivation 1 1.2 Aufbau der Arbeit 4 2 Grundlagen 5 2.1 OpenStreetMap 5 2.1.1 Ablauf der Erstellung von OSM-Karten 6 2.1.2 Mapnik 9 2.2 Web Services 12 2.2.1 OGC Web Processing Services 12 2.2.2 Web Generalization Services 14 2.2.3 Verkettung von OGC Web Services 16 2.3 Kartographische Generalisierung 17 2.3.1 Konzeptionelle Modellvorstellungen 18 2.3.2 Generalisierungsoperatoren 22 3 OpenStreetMap & Generalisierung – aktueller Stand 24 3.1 Allgemeine Analyse und Kritik 25 3.2 OSM & konzeptionelle Modelle 28 4 Theoretische Überlegungen 31 4.1 Einbindung des WebGen-WPS 32 4.1.1 Direkteinbindung des WebGen-WPS 32 4.1.2 Einbindung von WebGen-WPS für „MRDB-OSM“ 34 4.2 PostGIS-Funktionen 36 4.3 OpenStreetMap - Generalisierungscommunity 38 5 Implementierungen & Ergebnisse 40 5.1 Technische Voraussetzungen 41 5.1.1 Systemvoraussetzungen 41 5.1.2 Testgebiet 41 5.2 Einbindung des WebGen-WPS in Mapnik 42 5.2.1 Einbindung in den automatischen Prozess 42 5.2.1.1 Allgemeiner Programmablauf 43 5.2.1.2 Implementierungsansätze 44 5.2.2 Praktische Umsetzung einer „MRDB-OSM“ 47 5.2.2.1 Verfahrensablauf 48 5.2.2.2 Polygonvereinfachung 51 5.2.2.3 Linienvereinfachung 57 5.3 Implementierung von PostGIS-Funktionen 59 5.3.1 Auswahl 59 5.3.2 Betonung 60 5.3.3 Linienvereinfachung 61 5.3.4 Polygonvereinfachung 61 6 Schlussfolgerungen und Ausblicke 65 6.1 Diskussion der Ergebnisse 65 6.2 Fazit 71 7 Quellennachweise 72 7.1 Literaturverzeichnis 72 7.2 Internetquellennachweis (ohne eindeutige Autoren) 77 8 Anhang 79 / OpenStreetMap (OSM) has established very quickly since its founding in 2004 and has become a suitable alternative to similar commercial applications. This success is clearly due to the revolutionary concept of the project. Spatial data is collected by members world-wide and is provided to the project OSM. The underlying license aggreement ensures that OSM-Data is freely available and can be used free of charge. Primarily, the idea of independence from proprietary data has led to strong, still growing, global participation. Resulting from that, the available data is now achieving high density and accuracy. Visualizations in form of interactive, freely scalable maps of the world, which are constructed by the fully automated software solutions Mapnik and Osmarender are most common. In consequence cartographic principles and rules must be formalized and implemented. Particularly with respect to cartographic generalization, some serious faults appear in the corresponding implementations. This is the starting point of this diploma thesis. Based on an analysis of the current state, actual existing deficiencies are identified and then examined for possibilities to integrate generalization functionalities. Recent developments aim at the deployment of interoperable systems in the context of cartographic generalization, with the intention of providing generalization functionalities over the Internet. This is based on Web Processing Services (WPS) that where developed by the Open Geospatial Consortium (OGC). They enable the analysis and processing of spatial data. In this context, Web Generalization Services (Webgen-WPS) are examined for possible integration into the software solutions and represent therefore a central object of investigation within that examination. Mapnik provides, not least through its “open source” code, ideal conditions for those implementations. Mapnik uses the “open source” spatial database PostGIS for the processing of OSM-Data, which also provides capabilities to analyze and process spatial data. In this context is examined in addition, to what extent the features have potential for implementation of cartographic generalization.:Inhaltsverzeichnis Aufgabenstellung ii Zusammenfassung iii Abstract iv Abbildungsverzeichnis viii Tabellenverzeichnis ix Abkürzungsverzeichnis x 1 Einleitung 1 1.1 Motivation 1 1.2 Aufbau der Arbeit 4 2 Grundlagen 5 2.1 OpenStreetMap 5 2.1.1 Ablauf der Erstellung von OSM-Karten 6 2.1.2 Mapnik 9 2.2 Web Services 12 2.2.1 OGC Web Processing Services 12 2.2.2 Web Generalization Services 14 2.2.3 Verkettung von OGC Web Services 16 2.3 Kartographische Generalisierung 17 2.3.1 Konzeptionelle Modellvorstellungen 18 2.3.2 Generalisierungsoperatoren 22 3 OpenStreetMap & Generalisierung – aktueller Stand 24 3.1 Allgemeine Analyse und Kritik 25 3.2 OSM & konzeptionelle Modelle 28 4 Theoretische Überlegungen 31 4.1 Einbindung des WebGen-WPS 32 4.1.1 Direkteinbindung des WebGen-WPS 32 4.1.2 Einbindung von WebGen-WPS für „MRDB-OSM“ 34 4.2 PostGIS-Funktionen 36 4.3 OpenStreetMap - Generalisierungscommunity 38 5 Implementierungen & Ergebnisse 40 5.1 Technische Voraussetzungen 41 5.1.1 Systemvoraussetzungen 41 5.1.2 Testgebiet 41 5.2 Einbindung des WebGen-WPS in Mapnik 42 5.2.1 Einbindung in den automatischen Prozess 42 5.2.1.1 Allgemeiner Programmablauf 43 5.2.1.2 Implementierungsansätze 44 5.2.2 Praktische Umsetzung einer „MRDB-OSM“ 47 5.2.2.1 Verfahrensablauf 48 5.2.2.2 Polygonvereinfachung 51 5.2.2.3 Linienvereinfachung 57 5.3 Implementierung von PostGIS-Funktionen 59 5.3.1 Auswahl 59 5.3.2 Betonung 60 5.3.3 Linienvereinfachung 61 5.3.4 Polygonvereinfachung 61 6 Schlussfolgerungen und Ausblicke 65 6.1 Diskussion der Ergebnisse 65 6.2 Fazit 71 7 Quellennachweise 72 7.1 Literaturverzeichnis 72 7.2 Internetquellennachweis (ohne eindeutige Autoren) 77 8 Anhang 79