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.

High-resolution reconstruction of Holocene climate variability and environmental changes in the North Pacific using bivalve shells

Bivalve mollusk shells are useful tools for multi-species and multi-proxy paleoenvironmental reconstructions with a high temporal and spatial resolution. Past environmental conditions can be reconstructed from shell growth and stable oxygen and carbon isotope ratios, which present an archive for temperature, freshwater fluxes and primary productivity. The purpose of this thesis is the reconstruction of Holocene climate and environmental variations in the North Pacific with a high spatial and temporal resolution using marine bivalve shells. This thesis focuses on several different Holocene time periods and multiple regions in the North Pacific, including: Japan, Alaska (AK), British Columbia (BC) and Washington State, which are affected by the monsoon, Pacific Decadal Oscillation (PDO) and El Niño/Southern Oscillation (ENSO). Such high-resolution proxy data from the marine realm of mid- and high-latitudes are still rare. Therefore, this study contributes to the optimization and verification of climate models. However, before using bivalves for environmental reconstructions and seasonality studies, life history traits must be well studied to temporally align and interpret the geochemical record. These calibration studies are essential to ascertain the usefulness of selected bivalve species as paleoclimate proxy archives. This work focuses on two bivalve species, the short-lived Saxidomus gigantea and the long-lived Panopea abrupta. Sclerochronology and oxygen isotope ratios of different shell layers of P. abrupta were studied in order to test the reliability of this species as a climate archive. The annual increments are clearly discernable in umbonal shell portions and the increments widths should be measured in these shell portions. A reliable reconstruction of paleotemperatures may only be achieved by exclusively sampling the outer shell layer of multiple contemporaneous specimens. Life history traits (e.g., timing of growth line formation, duration of the growing season and growth rates) and stable isotope ratios of recent S. gigantea from AK and BC were analyzed in detail. Furthermore, a growth-temperature model based on S. gigantea shells from Alaska was established, which provides a better understanding of the hydrological changes related to the Alaska Coastal Current (ACC). This approach allows the independent measurement of water temperature and salinity from variations in the width of lunar daily growth increments of S. gigantea. Temperature explains 70% of the variability in shell growth. The model was calibrated and tested with modern shells and then applied to archaeological specimens. The time period between 988 and 1447 cal yrs BP was characterized by colder (~1-2°C) and much drier (2-5 PSU) summers, and a likely much slower flowing ACC than at present. In contrast, the summers during the time interval of 599-1014 cal yrs BP were colder (up to 3°C) and fresher (1-2 PSU) than today. The Aleutian Low may have been stronger and the ACC was probably flowing faster during this time.