Class Central is learner-supported. When you buy through links on our site, we may earn an affiliate commission.

YouTube

Constant Factor Approximations to Edit Distance in Nearly Linear Time

Association for Computing Machinery (ACM) via YouTube

Overview

Save Big on Coursera Plus. 7,000+ courses at $160 off. Limited Time Only!
Explore constant factor approximations to edit distance in nearly linear time through this 24-minute conference talk merging two papers. Delve into the main results and approximation techniques for edit distance. Learn about partitioning strings into windows, reducing to non-crossing matching, and handling dense graphs using triangle inequality. Discover methods for sparse graphs via "seed-and-expand" and union of disjoint bl-cliques. Examine searching for matches in both sparse and dense cases using the CDGKS algorithm. Investigate multiple levels in the sparse case and recap the key concepts presented by researchers from Stanford University, Charles University, and Rutgers University.

Syllabus

Intro
Approx ED
Main Result
Approximating ED
Partition strings into windows
Step 0: Reduction to non-crossing matching
Note: this step crucially uses triangle inequality!
Step 1: Dense graphs via triangle inequality
Sparse graphs via "seed-and-expand"
Union of disjoint bl-cliques
Searching for matches [KS]
Sparse case CDGKS
Dense case CDGKS
Multiple levels - sparse case [KS]
Recap

Taught by

Association for Computing Machinery (ACM)

Reviews

Start your review of Constant Factor Approximations to Edit Distance in Nearly Linear Time

Never Stop Learning.

Get personalized course recommendations, track subjects and courses with reminders, and more.

Someone learning on their laptop while sitting on the floor.