Show simple item record

2015-10-26Dissertation DOI: 10.18452/17338
Scalable time series similarity search for data analytics
dc.contributor.authorSchäfer, Patrick
dc.date.accessioned2017-06-18T14:24:45Z
dc.date.available2017-06-18T14:24:45Z
dc.date.created2015-10-30
dc.date.issued2015-10-26
dc.identifier.urihttp://edoc.hu-berlin.de/18452/17990
dc.description.abstractEine Zeitreihe ist eine zeitlich geordnete Folge von Datenpunkten. Zeitreihen werden typischerweise über Sensormessungen oder Experimente erfasst. Sensoren sind so preiswert geworden, dass sie praktisch allgegenwärtig sind. Während dadurch die Menge an Zeitreihen regelrecht explodiert, lag der Schwerpunkt der Forschung in den letzten Jahrzehnten auf der Analyse von (a) vorgefilterten und (b) kleinen Zeitreihendatensätzen. Die Analyse realer Zeitreihendatensätze wirft zwei Probleme auf: Erstens setzen aktuelle Ähnlichkeitsmodelle eine Vorfilterung der Zeitreihen voraus. Das beinhaltet die Extraktion charakteristischer Teilsequenzen und das Entfernen von Rauschen. Diese Vorverarbeitung muss durch einen Spezialisten erfolgen. Sie kann zeit- und kostenintensiver als die anschließende Analyse und für große Datensätze unrentabel werden. Zweitens führte die Verbesserung der Genauigkeit aktueller Ähnlichkeitsmodelle zu einem unverhältnismäßig hohen Anstieg der Komplexität (quadratisch bis biquadratisch). Diese Dissertation behandelt beide Probleme. Es wird eine symbolische Zeitreihenrepräsentation vorgestellt. Darauf aufbauend werden drei verschiedene Ähnlichkeitsmodelle eingeführt. Diese erweitern den aktuellen Stand der Forschung insbesondere dadurch, dass sie vorverarbeitungsfrei, unempfindlich gegenüber Rauschen und skalierbar sind. Anhand von 91 realen Datensätzen und Benchmarkdatensätzen wird zusätzlich gezeigt, dass die hier eingeführten Modelle auf den meisten Datenätzen die höchste Genauigkeit im Vergleich zu 15 aktuellen Ähnlichkeitsmodellen liefern. Sie sind teilweise drei Größenordnungen schneller und benötigen kaum Vorfilterung.ger
dc.description.abstractA time series is a collection of values sequentially recorded from sensors or live observations over time. Sensors for recording time series have become cheap and omnipresent. While data volumes explode, research in the field of time series data analytics has focused on the availability of (a) pre-processed and (b) moderately sized time series datasets in the last decades. The analysis of real world datasets raises two major problems: Firstly, state-of-the-art similarity models require the time series to be pre-processed. Pre-processing aims at extracting approximately aligned characteristic subsequences and reducing noise. It is typically performed by a domain expert, may be more time consuming than the data mining part itself, and simply does not scale to large data volumes. Secondly, time series research has been driven by accuracy metrics and not by reasonable execution times for large data volumes. This results in quadratic to biquadratic computational complexities of state-of-the-art similarity models. This dissertation addresses both issues by introducing a symbolic time series representation and three different similarity models. These contribute to state of the art by being pre-processing-free, noise-robust, and scalable. Our experimental evaluation on 91 real-world and benchmark datasets shows that our methods provide higher accuracy for most datasets when compared to 15 state-of-the-art similarity models. Meanwhile they are up to three orders of magnitude faster, require less pre-processing for noise or alignment, or scale to large data volumes.eng
dc.language.isoeng
dc.publisherHumboldt-Universität zu Berlin, Mathematisch-Naturwissenschaftliche Fakultät
dc.rightsNamensnennung - Keine kommerzielle Nutzung
dc.rights.urihttp://creativecommons.org/licenses/by-nc/3.0/de/
dc.subjectData Miningger
dc.subjectZeitreihenger
dc.subjectSkalierbarger
dc.subjectÄhnlichkeitssucheger
dc.subjectTime Serieseng
dc.subjectScalableeng
dc.subjectSimilarity Searcheng
dc.subjectData Analyticseng
dc.subject.ddc004 Informatik
dc.titleScalable time series similarity search for data analytics
dc.typedoctoralThesis
dc.identifier.urnurn:nbn:de:kobv:11-100233106
dc.identifier.doihttp://dx.doi.org/10.18452/17338
dc.identifier.alephidBV042958078
dc.date.accepted2015-10-19
dc.contributor.refereeReinefeld, Alexander
dc.contributor.refereeLeser, Ulf
dc.contributor.refereeAndrzejak, Artur
dc.subject.dnb28 Informatik, Datenverarbeitung
dc.subject.rvkSK 845
dc.subject.rvkST 265
local.edoc.pages175
local.edoc.type-nameDissertation
local.edoc.institutionMathematisch-Naturwissenschaftliche Fakultät

Show simple item record