Differences

This shows you the differences between two versions of the page.

--- time_series:index [2014/12/21 18:03] – phreazer
+++ time_series:index [2014/12/21 18:19] – [DTW Spezifika] phreazer
@@ Line 5: / Line 5: @@
 Indizieren schränkt den Suchraum auf eine bestimmte Nachbarschaft der Anfrage/Query ein. Dazu werden Lower Bounds benutzt. Ein Beispiel dafür ist iSax_MinDist, die Folgen prunt, basierend auf Bereichsintervalle, die für quantisierte Zeitreihen bestimmt wurden.
+Zusätzliche Beschleunigung kann durch approximierte Lower Bounds erreicht werden, bei denen es aber ein Anteil falscher Ergebnisse gibt.
+===== DTW Spezifika =====
 Komplexität für die Berechnung von DTW zwischen 2 Zeitreihen liegt bei Verwendung eines Warping Windows w bei O(nw).
+Beschleunigung:
+- LB_Keogh: Lower Bound Funktion mit Komplexität von O(n)
+- LB_PAA: PAA + ähnliche Weise wie LB_Keogh nur für kleineres n
+- iSAX:
+Durch PAA erhält man n-dimensionalen Raum, der mit einem R-Baum indexiert werden kann. Index enthält MBR, in denen ähnliche Sequenzen gruppiert werden. Bei einer Anfrage werden die Sequenzen gefunden, die nahe an Q liegen, basierend auf der Distanz zum MBR. (Keogh and Ratanamahatana 2005).
+Bei iSax werden zusätzlich zu PAA Zeitreihen quantisiert und in Folgen von Symbolen umgewandelt. Größe des Alphabets wird automatisch angepasst bei der Indexkonstruktion. iSAX_MinDist metrik (Shieh and Keogh (2008)).
+IDDTW
+Nur DTW für die Zeitreihen berechnen, die wahrscheinlich ähnlich sind. Wahrscheinlichkeit bestimmt sich anhand DTW von downgesampleten Zeitreihen. So lange Kandidaten untersuchen, bis diese ausgeschlossen werden können oder nicht. (Chu et al., 2002).
+Paper source (Improving the Efficiency of Traditional DTW Accelerators):
+http://people.irisa.fr/Romain.Tavenard/pdf/kais_13_tavenard.pdf
 (Longest Common Subsequence: Eigenschaft: Outlier werden nicht gematcht)