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:13] – 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)).
 (Longest Common Subsequence: Eigenschaft: Outlier werden nicht gematcht)