Authors:	Hundt, Christian
Title:	Efficient subsequence alignment of time series
Online publication date:	16-Oct-2015
Year of first publication:	2015
Language:	german
Abstract:	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. Time series occur almost everywhere. A large variety of domains deal with the recording and processing of continuously measured data streams including all areas of natural science, medicine and finance. The vast growth of recorded data produced by automated monitoring systems or integrated sensors establishes the need for exceedingly fast algorithms in theory and practice. Hence, the focus of this thesis is the efficient computation of subsequence alignments in streams of time series. Many high-level algorithms amongst other anomaly detection, motif retrieval or the unsupervised extraction of major buildings blocks of time series make excessive use of subsequence alignments and thus there is a urgent need for fast implementations. This thesis consists of three frameworks to address this challenge. This includes four subsequence alignment algorithms and their parallelizations on CUDA-enabled devices, a stream segmentation algorithm and a unified framework for the treatment of Lie group-valued time series:rnrnFirstly, we provide a complete port of the fastest single-threaded implementation of one-nearest-neighbour search, namely the UCR-Suite, to CUDA-enabled accelerators. The proposed implementation includes a novel computation scheme for the calculation of local alignment scores under z-normalized rnEuclidean distance that can be applied on any concurrent hardware that features a Fast Fourier Transform. Further, we provide an SIMT-compliant mapping of UCR-Suite's lower bound cascade for the efficient computation of local alignment scores under the Dynamic Time Warping (DTW) similarity measure. Both CUDA-parallelizations outperform the state-of-the art by one to two orders-of-magnitude.rnrnSecondly, we investigate two linear time approximations for the elastic alignment of subsequence candidates. On the one hand, we provide an SIMT-compliant relaxation scheme for greedily relaxed DTW and its efficient parallelization on massively parallel devices. On the other hand, we introduce a novel subsequence measure, the Gliding Elastic Match (GEM), that can be computed with the same asymptotic complexity as greedily relaxed DTW but in contrast offers a full relaxation of the penalty matrix. Further advantages of the GEM approach include invariance against time-dependent trends on the measurement-axis and invariance against uniform scaling of the time-axis. Moreover, an extension of GEM to supervised multi-shape segmentation of streams is provided and evaluated on motion-tracking data. Both CUDA-parallelizations feature speedups of up to two orders-of-magnitude in comparison to sequential code.rnrnThirdly, the treatment of time series is usually limited to real-valued data in the literature. We provide a unified approach to handle Lie group-valued time series. Building upon this, notions of similarity in the group of rotations SO(3) and rigid transformations SE(3) are established. Furthermore, memory-efficient representations and extensions of elastic measures to handle group elements are discussed. Finally, we verify our theoretical ideas on motion sensor data.rn
DDC:	004 Informatik 004 Data processing
Institution:	Johannes Gutenberg-Universität Mainz
Department:	FB 08 Physik, Mathematik u. Informatik
Place:	Mainz
ROR:	https://ror.org/023b0x485
DOI:	http://doi.org/10.25358/openscience-1269
URN:	urn:nbn:de:hebis:77-41802
Version:	Original work
Publication type:	Dissertation
License:	In Copyright
Information on rights of use:	https://rightsstatements.org/vocab/InC/1.0/
Appears in collections:	JGU-Publikationen