time_series:index

Differences

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

Link to this comparison view

Both sides previous revisionPrevious revision
Next revision
Previous revision
time_series:index [2014/12/21 18:13] phreazertime_series:index [2015/01/04 18:56] (current) – [DTW Spezifika] phreazer
Line 7: Line 7:
  
 Zusätzliche Beschleunigung kann durch approximierte Lower Bounds erreicht werden, bei denen es aber ein Anteil falscher Ergebnisse gibt. Zusätzliche Beschleunigung kann durch approximierte Lower Bounds erreicht werden, bei denen es aber ein Anteil falscher Ergebnisse gibt.
 +
 +
 +Weber et al. haben gezeigt, dass die Performanz eines Indexierungsschemas dem eines sequentiellen Scans entspricht, wenn es mehrere Dimensionen gibt.
 +
 +
  
 ===== DTW Spezifika ===== ===== DTW Spezifika =====
 +**Lemire:**
 +Wenn die Distanz keine Metrik ist, oder die Anzahl der Dimensionen zu groß wird, so wird eine Begrenzungstechnik verwendet wie bspw. beim Generic Multimedia Object Indexing (GEMINI). False Positives werden schnell ausgeschlossen, indem eine untere Schranke berechnet wird.
 +
 +LB_Keogh: Wenn die erste untere Schranke ausreicht einen Kandidaten zu eliminieren, wird die Berechnung abgebrochen. Ansonsten wird die Zeitreihe ein weiteres mal bearbeitet, um die untere Schranke zu erhöhen. Wenn die zweite untere Schranke groß genug ist, wird der Kandidat geprunt, ansonsten wird die DTW-Distanz berechnet.
 +
  
 Komplexität für die Berechnung von DTW zwischen 2 Zeitreihen liegt bei Verwendung eines Warping Windows w bei O(nw). Komplexität für die Berechnung von DTW zwischen 2 Zeitreihen liegt bei Verwendung eines Warping Windows w bei O(nw).
Line 20: Line 30:
  
 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)). 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) (Longest Common Subsequence: Eigenschaft: Outlier werden nicht gematcht)
  • time_series/index.1419181994.txt.gz
  • Last modified: 2014/12/21 18:13
  • by phreazer