Differences
This shows you the differences between two versions of the page.
Next revision | Previous revisionLast revisionBoth sides next revision | ||
time_series:index [2014/12/21 16:37] – angelegt phreazer | time_series:index [2014/12/21 18:19] – [DTW Spezifika] phreazer | ||
---|---|---|---|
Line 1: | Line 1: | ||
====== Indexieren von Zeitreihen ====== | ====== Indexieren von Zeitreihen ====== | ||
+ | Finden eines effizienten Algorithmus, | ||
+ | |||
+ | Für das einfache indexieren sollte es sich beim Distanzmaß um eine Metrik handeln. Es gibt aber interessante Distanzmaße, | ||
+ | |||
+ | Indizieren schränkt den Suchraum auf eine bestimmte Nachbarschaft der Anfrage/ | ||
+ | |||
+ | 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, | ||
+ | |||
+ | Paper source (Improving the Efficiency of Traditional DTW Accelerators): | ||
+ | http:// | ||
+ | |||
+ | (Longest Common Subsequence: | ||
+ | |||
+ | Similarity Retrieval: | ||
+ | |||
+ | - Range Query: Alle Zeitreihen finden, die in Epsilon Umgebung liegen | ||
+ | - NN Query: K Ähnlichste Zeitreihen finden | ||
+ | |||
+ | LB Distanz: | ||
+ | PAA benutzen und Lower Bound berechnen | ||
+ | |||
+ | |||