Die zuverlässige Ortung von Fahrgästen und Fahrzeugen bildet die Grundlage für Anwendungen im Öffentlichen Personenverkehr (ÖPV) im Rahmen intelligenter Verkehrssysteme. Unter den gegebenen Systembedingungen stoßen funkbasierte Ortungssysteme auf Grund von Abschattungen oder Mehrwegeausbreitungen an ihre Grenzen. Zusätzliche Ortungsinformationen liefern Beschleunigungssensoren. Diese Arbeit entwirft Methoden zur Nutzung dieser Sensorinformationen zur Stützung von Navigationsfunktionen im ÖPV. Ein wesentlicher Gegenstand dieser Arbeit ist der vertiefte Vergleich von theoretisch vorhandenen und praktisch messbaren Fahrzeugsignalen mit den durch die nutzende Person beeinflussten Signalen einer mobilen Sensorplattform (zum Beispiel Smartphone, entsprechend ausgestattetes Nutzermedium). Darauf aufbauend wird ein neues Verfahren zur Schätzung von Bewegungsmodus (d.h. Verkehrsmittelwahl) und -zustand (detaillierte Bewegungsform, z. B. Kurvenfahrt) entwickelt. Dazu wird ein geschichtetes Bewegungszustandsmodell entworfen, welches die verschiedenen in einer ÖPV-Umgebung zu betrachtenden Bewegungszustände und -modi definiert und miteinander verbindet. Dieses Modell ist Grundlage für den in der Arbeit entwickelten und genutzten Algorithmus zur Bewegungszustandserkennung. Anhand von Beispielmessungen von Fahrzeug- (Dresdner Messstraßenbahn, Bus der DVB AG) und Personenbewegungen wird dieses Vorgehen auf seine Anwendbarkeit hin untersucht. Die erstellten Klassifikatoren werden mit dem in dieser Arbeit entwickelten Ansatz wahrscheinlichkeitsbasierter Güteschranken bewertet. Als Teil der Laborumgebung der Professur „Informationstechnik für Verkehrssysteme“ an der TU Dresden zur originalgetreuen Wiederholung von verkehrstelematischen Messfahrten für Sensor- und Softwaretests wird die Reproduktion von Beschleunigungssignalen umgesetzt und diskutiert. Konkrete Beispiele zur Stützung von Navigationsfunktionen im ÖPV auf Basis von Beschleunigungssignalen werden ebenfalls dargestellt.

Die Netzwerkanalyse zielt darauf ab, nicht-triviale Erkenntnisse aus vernetzten Daten zu gewinnen. Beispiele für diese Erkenntnisse sind die Wichtigkeit einer Entität im Verhältnis zu anderen nach bestimmten Kriterien oder das Finden des am besten geeigneten Partners für jeden Teilnehmer eines Netzwerks - bekannt als Maximum Weighted Matching (MWM). Da der Begriff der Wichtigkeit an die zu betrachtende Anwendung gebunden ist, wurden zahlreiche Zentralitätsmaße eingeführt. Diese Maße stammen hierbei aus Jahrzehnten, in denen die Rechenleistung sehr begrenzt war und die Netzwerke im Vergleich zu heute viel kleiner waren. Heute sind massive Netzwerke mit Millionen von Kanten allgegenwärtig und eine triviale Berechnung von Zentralitätsmaßen ist oft zu zeitaufwändig. Darüber hinaus ist die Suche nach der Gruppe von k Knoten mit hoher Zentralität eine noch kostspieligere Aufgabe. Skalierbare Algorithmen zur Identifizierung hochzentraler (Gruppen von) Knoten in großen Graphen sind von großer Bedeutung für eine umfassende Netzwerkanalyse. Heutigen Netzwerke verändern sich zusätzlich im zeitlichen Verlauf und die effiziente Aktualisierung der Ergebnisse nach einer Änderung ist eine Herausforderung. Effiziente dynamische Algorithmen sind daher ein weiterer wesentlicher Bestandteil moderner Analyse-Pipelines. Hauptziel dieser Arbeit ist es, skalierbare algorithmische Lösungen für die zwei oben genannten Probleme zu finden. Die meisten unserer Algorithmen benötigen Sekunden bis einige Minuten, um diese Aufgaben in realen Netzwerken mit bis zu Hunderten Millionen von Kanten zu lösen, was eine deutliche Verbesserung gegenüber dem Stand der Technik darstellt. Außerdem erweitern wir einen modernen Algorithmus für MWM auf dynamische Graphen. Experimente zeigen, dass unser dynamischer MWM-Algorithmus Aktualisierungen in Graphen mit Milliarden von Kanten in Millisekunden bewältigt. / Network analysis aims to unveil non-trivial insights from networked data by studying relationship patterns between the entities of a network. Among these insights, a popular one is to quantify the importance of an entity with respect to the others according to some criteria. Another one is to find the most suitable matching partner for each participant of a network knowing the pairwise preferences of the participants to be matched with each other - known as Maximum Weighted Matching (MWM). Since the notion of importance is tied to the application under consideration, numerous centrality measures have been introduced. Many of these measures, however, were conceived in a time when computing power was very limited and networks were much smaller compared to today's, and thus scalability to large datasets was not considered. Today, massive networks with millions of edges are ubiquitous, and a complete exact computation for traditional centrality measures are often too time-consuming. This issue is amplified if our objective is to find the group of k vertices that is the most central as a group. Scalable algorithms to identify highly central (groups of) vertices on massive graphs are thus of pivotal importance for large-scale network analysis. In addition to their size, today's networks often evolve over time, which poses the challenge of efficiently updating results after a change occurs. Hence, efficient dynamic algorithms are essential for modern network analysis pipelines. In this work, we propose scalable algorithms for identifying important vertices in a network, and for efficiently updating them in evolving networks. In real-world graphs with hundreds of millions of edges, most of our algorithms require seconds to a few minutes to perform these tasks. Further, we extend a state-of-the-art algorithm for MWM to dynamic graphs. Experiments show that our dynamic MWM algorithm handles updates in graphs with billion edges in milliseconds.

Matching of concepts with variables (concept patterns) is a relatively new operation that has been introduced in the context of description logics, originally to help filter out unimportant aspects of large concepts appearing in industrial-strength knowledge bases. Previous work has concentrated on (sub-)languages of CLASSIC, which in particular do not allow for existential restrictions. In this work, we present sound and complete decision algorithms for the solvability of matching problems and for computing sets of matchers for matching problems in description logics with existential restrictions.

Product matching in e-commerce is an area that faces more and more challenges with growth in the e-commerce marketplace as well as variation in the quality of data available online for each product. Product matching for e-commerce provides competitive possibilities for vendors and flexibility for customers by identifying identical products from different sources. Traditional methods in product matching are often conducted through rule-based methods and methods tackling the issue through machine learning usually do so through unimodal systems. Moreover, existing methods would tackle the issue through product identifiers which are not always unified for each product. This thesis provides multimodal approaches through product name, description, and image to the problem area of product matching that outperforms unimodal approaches. Three multimodal approaches were taken, one unsupervised and two supervised. The unsupervised approach uses straight-forward embedding space to nearest neighbor search that provides better results than unimodal approaches. One of the supervised multimodal approaches uses Siamese network on the embedding space which outperforms the unsupervised multi- modal approach. Finally, the last supervised approach instead tackles the issue by exploiting distance differences in each modality through logistic regression and a decision system that provided the best results. / Produktmatchning inom e-handel är ett område som möter fler och fler utmaningar med hänsyn till den tillväxt som e-handelsmarknaden undergått och fortfarande undergår samt variation i kvaliteten på den data som finns tillgänglig online för varje produkt. Produktmatchning inom e-handel är ett område som ger konkurrenskraftiga möjligheter för leverantörer och flexibilitet för kunder genom att identifiera identiska produkter från olika källor. Traditionella metoder för produktmatchning genomfördes oftast genom regelbaserade metoder och metoder som utnyttjar maskininlärning gör det vanligtvis genom unimodala system. Dessutom utnyttjar mestadels av befintliga metoder produktidentifierare som inte alltid är enhetliga för varje produkt mellan olika källor. Denna studie ger istället förslag till multimodala tillvägagångssätt som istället använder sig av produktnamn, produktbeskrivning och produktbild för produktmatchnings-problem vilket ger bättre resultat än unimodala metoder. Tre multimodala tillvägagångssätt togs, en unsupervised och två supervised. Den unsupervised metoden använder embeddings vektorerna rakt av för att göra en nearest neighborsökning vilket gav bättre resultat än unimodala tillvägagångssätt. Ena supervised multimodal tillvägagångssätten använder siamesiska nätverk på embedding utrymmet vilket gav resultat som överträffade den unsupervised multimodala tillvägagångssättet. Slutligen tar den sista supervised metoden istället avståndsskillnader i varje modalitet genom logistisk regression och ett beslutssystem som gav bästa resultaten.

No description available.

Yes / This paper presents an approach to implement an automatically tuning antenna for optimising power transfer suitable for software defined radio (SDR). Automatic tuning is accomplished using a closed loop impedance tuning network comprising of an impedance sensor and control unit. The sensor provides the control unit with data on the transmit or receive power, and the algorithm is used to impedance of a T-network of LC components to optimize the antenna impedance to maximise power transmission or reception. The effectiveness of the proposed tuning algorithm in relation to impedance matching and convergence on the optimum matching network goal is shown to be superior compared with the conventional tuning algorithm. / This work is partially supported by innovation programme under grant agreement H2020-MSCA-ITN-2016 SECRET-722424 and the financial support from the UK Engineering and Physical Sciences Research Council (EPSRC) under grant EP/E022936/1

L'objet de cette thèse porte sur la conception et la réalisation de deux sources laser non linéaires accordables dans les domaines IR et UV, pour le raccordement de la sensibilité spectrale des détecteurs au moyen du radiomètre cryogénique du laboratoire commun de métrologie (LCM). La source IR est un oscillateur paramétrique optique (OPO) résonant sur les ondes pompe et signal (PRSRO), utilisant un cristal de niobate de lithium à inversion de domaines de polarisation dopé par 5% d'oxyde de magnésium (ppMgCLN). Pompé par un laser Ti:Al2O3 en anneau mono-fréquence et accordable, délivrant 500 mW de puissance utile autour de 795 nm, l'OPO possède un seuil d'oscillation de 110 mW. Une couverture spectrale continue entre 1 µm et 3.5 µm a été obtenue, avec des puissances de l'ordre du mW pour l'onde signal (1 µm à 1.5 µm) et des puissances comprises entre $20$ à $50$ mW pour l'onde complémentaire couvrant un octave de longueur d'onde IR entre 1.7 µm et 3.5 µm. La source UV est obtenue par doublage de fréquence en cavité externe du laser Ti:Al2O3, dans un cristal de triborate de lithium (LiB3O5). Un accord de phase en température à angle d'accord de phase fixé permet l'obtention d'une couverture spectrale comprise entre 390 nm et 405 nm. L'asservissement de la cavité de doublage sur la fréquence du laser Ti:Al2O3 par la méthode de Pound-Drever-Hall, ainsi qu'une adaptation de mode optimale, permet d'obtenir une puissance de 5.64 mW à 400 nm à partir de 480 mW de puissance fondamentale. / The work presented in this PhD dissertation details the strategy adopted to build two non-linear laser sources that are widely in the mid-infrared and blue-UV spectral ranges. These laser sources are needed for the traceability to SI units of coherent light irradiance measurements using a cryogenic radiometer of the using cryogenic radiometer of the Laboratoire commun de métrologie (LCM) .The infrared laser source is an optical parametric oscillator (OPO) resonating on the pump and signal wavelengths (PRSRO) and employing a periodically poled Lithium Niobate non-linear crystal doped with 5% magnesium oxide (ppMgCLN). The PRSRO is pumped by a single-frequency tunable bow-tie ring cavity Titanium-Sapphire laser (Ti:Al2O3) delivering 500 mW output power at 795 nm wavelength, , resulting in a power oscillation threshold of 110 mW. The PRSRO emission could continuously cover the spectral range from 1 µm to 3.5 µm. The level of output power achieved is of the order of 1 mW for the signal wave (1 µm to 1.5 µm) and between 20 mW and 50 mW for idler wave spanning an octave wavelength range (1.7 µm to 3.5 µm).The UV source based on the second harmonic generation on the Titanium-Sapphire tunable laser using an external enhancement cavity containing a critically phase-matched LBO non linear crystal (LiB3O5). Temperature-tuning of the phase-matching condition at a fixed crystal orientation leads to a wide tunability from 390 nm to 405 nm wavelength. The external cavity optical pathlength was actively locked to the laser frequency using a¨Pound-Drever-Hall servo, allowing to extract up to 6 mW power at 400 nm wavelength with a 480 mW pump power. Despite a perfect mode-matching efficiency, the power performance was limited by the poor nonlinear impedance matching of the resonator, due to both the weak nonlinearity of the crystal and the low incoming laser power.

L’objet de cette thèse est de développer des méthodologies permettant d’identifier la distribution spatiale des valeurs de perméabilité dans des échantillons de roches. Nous avons tout d’abord développé en laboratoire des expériences d’injection de fluide miscible très visqueux dans des échantillons initialement saturés par une saumure peu visqueuse. Pendant l’injection, l’évolution au cours du temps de la pression différentielle entre les deux faces de l’échantillon a été enregistrée par des capteurs de pression. En outre, des mesures scanner ont fourni une carte 3D de la porosité ainsi que des cartes 3D décrivant la distribution spatiale des concentrations dans l’échantillon à différents temps. Nous avons mis en place une méthode d’interprétation donnant directement le profil 1D de la perméabilité le long de la direction d’écoulement à partir de la pression différentielle mesurée au cours du temps. Cette méthode a été validée numériquement et expérimentalement. Puis, afin d’affiner la description de l’agencement des valeurs de perméabilité dans l’échantillon, c’est à dire d’obtenir un modèle 3D de perméabilité représentatif de l’échantillon, nous avons développé une méthodologie itérative de calage des pressions et des concentrations. Cette méthode passe par deux étapes : une optimisation simple pour capturer l’hétérogénéité dans la direction de l’écoulement et une optimisation complexe pour capturer l’hétérogénéité transverse. Cette méthode a été validée à partir de tests numériques. La méthode a été appliquée à deux des expériences d’injection de fluide visqueux. Nous avons pu alors déterminer des modèles de perméabilité capables de reproduire assez bien les données de pression et de concentration acquises pendant l’injection / The objective of this study is to develop new methodologies to identify the spatial distribution of permeability values inside the heterogeneous core samples. We developed laboratory viscous miscible displacements by injecting high viscosity glycerin into the core samples initially saturated by low viscosity brine. The pressure drop across the samples was measured as a function of time until breakthrough. Meanwhile, CT scan measurements provided a 3D porosity map plus several 3D maps of concentration distribution inside the core samples at different times. A simple permeability mapping technique was developed deducing a one-dimensional permeability profile along the flow direction from the measured pressure drop data. The method was validated with both numerical and laboratory experiments. To go beyond one-dimensional characterization of permeability into cores, we developed an iterative process for matching pressure and concentration data. This method consisted of two steps: a simple optimization for capturing the permeability heterogeneity along the flow direction axis and a complex optimization for capturing transversal permeability heterogeneities. The methodology was validated by numerical data. It was also applied to the data collected from two laboratory viscous miscible displacements. We showed that the final 3D permeability models reproduce well the measured pressure drop and concentration data

Dans cette thèse on considère deux modèles de calcul qui abordent des problèmes qui se posent lors du traitement des grosses données. Le premier modèle est le modèle de streaming. Lors du traitement des grosses données, un accès aux données de façon aléatoire est trop couteux. Les algorithmes de streaming ont un accès restreint aux données: ils lisent les données de façon séquentielle (par passage) une fois ou peu de fois. De plus, les algorithmes de streaming utilisent une mémoire d'accès aléatoire de taille sous-linéaire dans la taille des données. Le deuxième modèle est le modèle de communication. Lors du traitement des données par plusieurs entités de calcul situées à des endroits différents, l'échange des messages pour la synchronisation de leurs calculs est souvent un goulet d'étranglement. Il est donc préférable de minimiser la quantité de communication. Un modèle particulier est la communication à sens unique entre deux participants. Dans ce modèle, deux participants calculent un résultat en fonction des données qui sont partagées entre eux et la communication se réduit à un seul message. On étudie les problèmes suivants: 1) Les couplages dans le modèle de streaming. L'entrée du problème est un flux d'arêtes d'un graphe G=(V,E) avec n=|V|. On recherche un algorithme de streaming qui calcule un couplage de grande taille en utilisant une mémoire de taille O(n polylog n). L'algorithme glouton remplit ces contraintes et calcule un couplage de taille au moins 1/2 fois la taille d'un couplage maximum. Une question ouverte depuis longtemps demande si l'algorithme glouton est optimal si aucune hypothèse sur l'ordre des arêtes dans le flux est faite. Nous montrons qu'il y a un meilleur algorithme que l'algorithme glouton si les arêtes du graphe sont dans un ordre uniformément aléatoire. De plus, nous montrons qu'avec deux passages on peut calculer un couplage de taille strictement supérieur à 1/2 fois la taille d'un couplage maximum sans contraintes sur l'ordre des arêtes. 2) Les semi-couplages en streaming et en communication. Un semi-couplage dans un graphe biparti G=(A,B,E) est un sous-ensemble d'arêtes qui couple tous les sommets de type A exactement une fois aux sommets de type B de façon pas forcement injective. L'objectif est de minimiser le nombre de sommets de type A qui sont couplés aux même sommets de type B. Pour ce problème, nous montrons un algorithme qui, pour tout 0<=ε<=1, calcule une O(n^((1-ε)/2))-approximation en utilisant une mémoire de taille Ô(n^(1+ε)). De plus, nous montrons des bornes supérieures et des bornes inférieurs pour la complexité de communication entre deux participants pour ce problème et des nouveaux résultats concernant la structure des semi-couplages. 3) Validité des fichiers XML dans le modèle de streaming. Un fichier XML de taille n est une séquence de balises ouvrantes et fermantes. Une DTD est un ensemble de contraintes de validité locales d'un fichier XML. Nous étudions des algorithmes de streaming pour tester si un fichier XML satisfait les contraintes décrites dans une DTD. Notre résultat principal est un algorithme de streaming qui fait O(log n) passages, utilise 3 flux auxiliaires et une mémoire de taille O(log^2 n). De plus, pour le problème de validation des fichiers XML qui décrivent des arbres binaires, nous présentons des algorithmes en un passage et deux passages qui une mémoire de taille sous-linéaire. 4) Correction d'erreur pour la distance du cantonnier. Alice et Bob ont des ensembles de n points sur une grille en d dimensions. Alice envoit un échantillon de petite taille à Bob qui, après réception, déplace ses points pour que la distance du cantonnier entre les points d'Alice et les points de Bob diminue. Pour tout k>0 nous montrons qu'il y a un protocole presque optimal de communication avec coût de communication Ô(kd) tel que les déplacements des points effectués par Bob aboutissent à un facteur d'approximation de O(d) par rapport aux meilleurs déplacements de d points. / In this PhD thesis, we consider two computational models that address problems that arise when processing massive data sets. The first model is the Data Streaming Model. When processing massive data sets, random access to the input data is very costly. Therefore, streaming algorithms only have restricted access to the input data: They sequentially scan the input data once or only a few times. In addition, streaming algorithms use a random access memory of sublinear size in the length of the input. Sequential input access and sublinear memory are drastic limitations when designing algorithms. The major goal of this PhD thesis is to explore the limitations and the strengths of the streaming model. The second model is the Communication Model. When data is processed by multiple computational units at different locations, then the message exchange of the participating parties for synchronizing their calculations is often a bottleneck. The amount of communication should hence be as little as possible. A particular setting is the one-way two-party communication setting. Here, two parties collectively compute a function of the input data that is split among the two parties, and the whole message exchange reduces to a single message from one party to the other one. We study the following four problems in the context of streaming algorithms and one-way two-party communication: (1) Matchings in the Streaming Model. We are given a stream of edges of a graph G=(V,E) with n=|V|, and the goal is to design a streaming algorithm that computes a matching using a random access memory of size O(n polylog n). The Greedy matching algorithm fits into this setting and computes a matching of size at least 1/2 times the size of a maximum matching. A long standing open question is whether the Greedy algorithm is optimal if no assumption about the order of the input stream is made. We show that it is possible to improve on the Greedy algorithm if the input stream is in uniform random order. Furthermore, we show that with two passes an approximation ratio strictly larger than 1/2 can be obtained if no assumption on the order of the input stream is made. (2) Semi-matchings in Streaming and in Two-party Communication. A semi-matching in a bipartite graph G=(A,B,E) is a subset of edges that matches all A vertices exactly once to B vertices, not necessarily in an injective way. The goal is to minimize the maximal number of A vertices that are matched to the same B vertex. We show that for any 0<=ε<=1, there is a one-pass streaming algorithm that computes an O(n^((1-ε)/2))-approximation using Ô(n^(1+ε)) space. Furthermore, we provide upper and lower bounds on the two-party communication complexity of this problem, as well as new results on the structure of semi-matchings. (3) Validity of XML Documents in the Streaming Model. An XML document of length n is a sequence of opening and closing tags. A DTD is a set of local validity constraints of an XML document. We study streaming algorithms for checking whether an XML document fulfills the validity constraints of a given DTD. Our main result is an O(log n)-pass streaming algorithm with 3 auxiliary streams and O(log^2 n) space for this problem. Furthermore, we present one-pass and two-pass sublinear space streaming algorithms for checking validity of XML documents that encode binary trees. (4) Budget-Error-Correcting under Earth-Mover-Distance. We study the following one-way two-party communication problem. Alice and Bob have sets of n points on a d-dimensional grid [Δ]^d for an integer Δ. Alice sends a small sketch of her points to Bob and Bob adjusts his point set towards Alice's point set so that the Earth-Mover-Distance of Bob's points and Alice's points decreases. For any k>0, we show that there is an almost tight randomized protocol with communication cost Ô(kd) such that Bob's adjustments lead to an O(d)-approximation compared to the k best possible adjustments that Bob could make.

L'imagerie médicale ultrasonore est une modalité en perpétuelle évolution et notamment en post-traitement où il s'agit d'améliorer la résolution et le contraste des images. Ces améliorations devraient alors aider le médecin à mieux distinguer les tissus examinés améliorant ainsi le diagnostic médical. Il existe déjà une large palette de techniques "hardware" et "software". Dans ce travail nous nous sommes focalisés sur la mise en oeuvre de techniques dites de "déconvolution aveugle", ces techniques temporelles utilisant l'enveloppe du signal comme information de base. Elles sont capables de reconstruire des images parcimonieuses, c'est-à-dire des images de diffuseurs dépourvues de bruit spéculaire. Les principales étapes de ce type de méthodes consistent en i) l'estimation aveugle de la fonction d'étalement du point (PSF), ii) l'estimation des diffuseurs en supposant l'environnement exploré parcimonieux et iii) la reconstruction d'images par reconvolution avec une PSF "idéale". La méthode proposée a été comparée avec des techniques faisant référence dans le domaine de l'imagerie médicale en utilisant des signaux synthétiques, des séquences ultrasonores réelles (1D) et images ultrasonores (2D) ayant des statistiques différentes. La méthode, qui offre un temps d'exécution très réduit par rapport aux techniques concurrentes, est adaptée pour les images présentant une quantité réduite ou moyenne des diffuseurs. / The ultrasonic imaging knows a continuous advance in the aspect of increasing the resolution for helping physicians to better observe and distinguish the examined tissues. There is already a large range of techniques to get the best results. It can be found also hardware or signal processing techniques. This work was focused on the post-processing techniques of blind deconvolution in ultrasound imaging and it was implemented an algorithm that works in the time domain and uses the envelope signal as input information for it. It is a blind deconvolution technique that is able to reconstruct reflectors and eliminate the diffusive speckle noise. The main steps are: the estimation of the point spread function (PSF) in a blind way, the estimation of reflectors using the assumption of sparsity for the examined environment and the reconstruction of the image by reconvolving the sparse tissue with an ideal PSF. The proposed method was tested in comparison with some classical techniques in medical imaging reconstruction using synthetic signals, real ultrasound sequences (1D) and ultrasound images (2D) and also using two types of statistically different images. The method is suitable for images that represent tissue with a reduced amount or average scatters. Also, the technique offers a lower execution time than direct competitors.