Sprungmarken

Servicenavigation

       

Hauptnavigation

Bereichsnavigation

Seminar

Algorithmische Komplexität von Ähnlichkeitsmaßen

im Wintersemester 2017/2018



Veranstalter:Jun.-Prof. Dr. Maike Buchin
Termine: Donnerstag10-12 UhrOH14-304
Beginn: 12.10.2017


[Aktuelles] [Inhalt] [Themen] [Literatur]


Aktuelles

<b>NEU</b> Der erste Besprechungstermin findet in der ersten Vorlesungswoche zum Seminartermin (12.10.2017 um 10:15 Uhr) statt. Dort werden auch die Themen vergeben.

<b>NEU</b> Man kann sich für das Seminar per Email an Prof. Buchin anmelden.

<b>NEU</b> Für jedes Thema wurde auch ein öffentlich zugänglicher Link auf PDF-Dokument gegeben.


Inhalt

In diesem Seminar beschäftigen wir uns mit der algorithmischen Komplexität einiger Maße auf Kurven und Sequenzen. In vielen Anwendungen interessiert man sich für den Vergleich von Kurven und Sequenzen anhand von Ähnlichkeitsmaßen, wie z.B. dem Fréchet Abstand, Dynamic Time Warping und der Edit Distanz. Zur Berechnung dieser Maße sind seit Langem quadratische Algorithmen bekannt, und es stellt sich die Frage nach schnelleren Algorithmen. Im Seminar wollen wir einige interessante sowohl obere als auch untere Schranken zur Berechnung der Maße sehen, die in den letzten Jahren entwickelt wurden.


Themen

Eine Auswahl von Themenblöcken finden Sie unten stehend:

  1. Berechnen des Fréchet Abstandes von zwei Kurven
    • Alt, Godau: Computing the Fréchet distance between two polygonal curves. IJCGA, 1995. PDF
    • Eiter, Mannila: Computing Discrete Fréchet Distance. TechReport, 1994. PDF
  2. Schnellere Algorithmen für den Fréchet Abstand
    • Gusfield: Algorithms on Strings, Trees, and Sequences. Kap. 12.7: The Four Russians Speed-Up. 1997. PDF
    • Agarwal, Avraham, Kaplan, Sharir: Computing the Discrete Fréchet Distance in Subquadratic Time. SODA, 2013. PDF
    • Buchin, Buchin, Meulemans, Mulzer: Four Soviets Walk the Dog - with an Application to Alt's Conjecture. SODA, 2014. PDF
  3. Schnellere Algorithmen für DTW und geometric edit distance
    • Agarwal, Fox, Pan, Ying: Approximating Dynamic Time Warping and Edit Distance for a Pair of Point Sequences. SoCG, 2016. PDF
    • Gold, Sharir: Dynamic Time Warping and Geometric Edit Distance: Breaking the Quadratic Barrier. ICALP, 2017. PDF
  4. Bedingte Untere Schranken
    • Bringmann: Why walking the dog takes time: Fréchet distance has no strongly subquadratic algorithms unless SETH fails. FOCS, 2014. PDF
    • Backurs, Indyk: Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false). STOC, 2015. PDF
    • Abboud, Backurs, Williams: Tight Hardness Results for LCS and Other Sequence Similarity Measures. FOCS, 2015. PDF1 PDF2
    • Bringmann, Künnemann: Quadratic Conditional Lower Bounds for String Problems and Dynamic Time Warping. FOCS, 2015. PDF
  5. Approximationsalgorithmen für den Fréchet Abstand
    • Driemel, Har-Peled, Wenk: Approximating the Fréchet distance for realistic curves in near linear time. SoCG, 2010. PDF
    • Bringmann, Mulzer: Approximability of the Discrete Fréchet Distance. SoCG, 2015. PDF
    • Bringmann, Künnemann: Improved Approximation for Fréchet Distance on c-packed Curves Matching Conditional Lower Bounds. ISAAC, 2015. PDF



Literatur


Letzte Änderung am 04.10.2017 von A. Krivošija