Efficient subsequence alignment of time series

Zeitreihen sind allgegenwärtig. Die Erfassung und Verarbeitung kontinuierlich gemessener Daten ist in allen Bereichen der Naturwissenschaften, Medizin und Finanzwelt vertreten. Das enorme Anwachsen aufgezeichneter Datenmengen, sei es durch automatisierte Monitoring-Systeme oder integrierte Sensoren, bedarf außerordentlich schneller Algorithmen in Theorie und Praxis. Infolgedessen beschäftigt sich diese Arbeit mit der effizienten Berechnung von Teilsequenzalignments. Komplexe Algorithmen wie z.B. Anomaliedetektion, Motivfabfrage oder die unüberwachte Extraktion von prototypischen Bausteinen in Zeitreihen machen exzessiven Gebrauch von diesen Alignments. Darin begründet sich der Bedarf nach schnellen Implementierungen. Diese Arbeit untergliedert sich in drei Ansätze, die sich dieser Herausforderung widmen. Das umfasst vier Alignierungsalgorithmen und ihre Parallelisierung auf CUDA-fähiger Hardware, einen Algorithmus zur Segmentierung von Datenströmen und eine einheitliche Behandlung von Liegruppen-wertigen Zeitreihen.rnrnDer erste Beitrag ist eine vollständige CUDA-Portierung der UCR-Suite, die weltführende Implementierung von Teilsequenzalignierung. Das umfasst ein neues Berechnungsschema zur Ermittlung lokaler Alignierungsgüten unter Verwendung z-normierten euklidischen Abstands, welches auf jeder parallelen Hardware mit Unterstützung für schnelle Fouriertransformation einsetzbar ist. Des Weiteren geben wir eine SIMT-verträgliche Umsetzung der Lower-Bound-Kaskade der UCR-Suite zur effizienten Berechnung lokaler Alignierungsgüten unter Dynamic Time Warping an. Beide CUDA-Implementierungen ermöglichen eine um ein bis zwei Größenordnungen schnellere Berechnung als etablierte Methoden.rnrnAls zweites untersuchen wir zwei Linearzeit-Approximierungen für das elastische Alignment von Teilsequenzen. Auf der einen Seite behandeln wir ein SIMT-verträgliches Relaxierungschema für Greedy DTW und seine effiziente CUDA-Parallelisierung. Auf der anderen Seite führen wir ein neues lokales Abstandsmaß ein, den Gliding Elastic Match (GEM), welches mit der gleichen asymptotischen Zeitkomplexität wie Greedy DTW berechnet werden kann, jedoch eine vollständige Relaxierung der Penalty-Matrix bietet. Weitere Verbesserungen umfassen Invarianz gegen Trends auf der Messachse und uniforme Skalierung auf der Zeitachse. Des Weiteren wird eine Erweiterung von GEM zur Multi-Shape-Segmentierung diskutiert und auf Bewegungsdaten evaluiert. Beide CUDA-Parallelisierung verzeichnen Laufzeitverbesserungen um bis zu zwei Größenordnungen.rnrnDie Behandlung von Zeitreihen beschränkt sich in der Literatur in der Regel auf reellwertige Messdaten. Der dritte Beitrag umfasst eine einheitliche Methode zur Behandlung von Liegruppen-wertigen Zeitreihen. Darauf aufbauend werden Distanzmaße auf der Rotationsgruppe SO(3) und auf der euklidischen Gruppe SE(3) behandelt. Des Weiteren werden speichereffiziente Darstellungen und gruppenkompatible Erweiterungen elastischer Maße diskutiert.

Die Nachkriegskarriere des "Schlächters von Lyon" - Klaus Barbie und die westlichen Nachrichtendienste

„Intelligent, anpassungsfähig, verschwiegen und zuverlässig“ – so charakterisierte der Bundesnachrichtendienst seinen Agenten „ADLER“ in dessen Abschaltmeldung. rnEin halbes Jahr – von Mai bis Dezember 1966 – hatte „ADLER“ in Diensten des westdeutschen Auslandsnachrichtendienstes gestanden und seine Vorgesetzten für ein monatliches Salär von 500 DM mit Informationen über linksgerichtete Entwicklungstendenzen in Bolivien versorgt. rnBereits zwölf Jahre zuvor, im November 1954, war der deutsche Agent, der nun für den BND in Lateinamerika spionierte, vom Ständigen Militärgericht in Lyon aufgrund seiner während des Zweiten Weltkrieges begangenen Kriegsverbrechen in Abwesenheit zum Tode verurteilt worden. rnDoch Klaus Barbie, der sich in seiner Funktion als Gestapo-Offizier zwischen 1942 und 1944 am Mord hunderter Mitglieder der französischen Résistance schuldig gemacht hatte, war zu diesem Zeitpunkt bereits „verschwunden“. Deutsche und französische Ermittlungsbehörden vermuteten ihn in Deutschland, dann wieder in Ägypten. Erst zu Beginn der siebziger Jahre wurde der in Bolivien lebende Geschäftsmann „Klaus Altmann“ als ehemaliger Gestapo-Chef von Lyon identifiziert. rnSchon damals stellten Serge und Beate Klarsfeld, die mit ihren Ermittlungen den „Fall Barbie“ über Nacht auf die Titelseiten der internationalen Presse katapultierten, die berechtigte Frage, wie es möglich war, dass der NS-Kriegsverbrecher nach 1945 nach Lateinamerika entkommen konnte. Sie nährten damit bereits existierende Gerüchte, der amerikanische Geheimdienst sei an der Protektion Barbies nicht unbeteiligt gewesen. Die Auslieferungsbemühungen verliefen zunächst im Sande. rnZu groß war die Unterstützung, die der NS-Verbrecher von Seiten bolivianischer Militärdiktaturen genoss. Erst 1983 sollte Barbie an Frankreich ausgewiesen und vor Gericht gestellt werden. Die Flut internationaler Presseartikel im Vorfeld des „Jahrhundert-Prozesses“, die eine Beziehung Barbies mit westlichen Geheimdiensten nahelegte, gab schließlich Anlass für einen Offenbarungseid. Aus Angst, Barbie könne vor Gericht für einen Skandal sorgen, flüchtete die US-Regierung nach vorne: Gestützt auf hunderte Seiten teils streng geheimer Dokumente der US-Armee konnte der im August 1983 von Seiten des US-Justizministeriums vorgelegte Untersuchungsbericht belegen, dass das Counter Intelligence Corps, der Heeresgeheimdienst der US-Armee, den NS-Täter im April 1947 als Informanten angeworben, ihn vor den französischen Ermittlern versteckt und ihn 1951 mit Hilfe einer geheimen „Rattenlinie“ unter dem Aliasnamen „Altmann“ aus Europa nach Bolivien geschleust hatte.rnDie vorliegende Dissertation rekapituliert erstmals vollständig die Beziehungen zwischen Barbie und westlichen Geheimdiensten nach 1945 auf Basis des mittlerweile zugänglichen Aktenmaterials in deutschen, französischen, britischen, bolivianischen und US-amerikanischen Archiven. Im Mittelpunkt steht dabei die Analyse der einzelnen Faktoren, die die Rekrutierung von NS-Tätern durch westliche Nachrichtendienste nach 1945 begünstigten. rn rn