Edit distance ED(r s): The minimum number of single-character edit operations(insertion/deletion/substitution )to transform r to s ●ED( sault, seraJI)=2 2/2/2021 Topk Search(@ ICD E2013
ED(r, s): The minimum number of single-character edit operations(insertion/deletion/substitution) to transform r to s. ED(srajit, seraji) = 2 Edit Distance 2/2/2021 TopkSearch @ ICDE2013 11/42
Dynamic Programming Insertion Deletion Match /Subsitition 1;=min(D1;+1,D11+1,D1,1+0/1} s r a j 1t 012|345|6 345 e|2 2345 r|3 1234|5 a4|32|1|234 j5|4|321|23 i[65|43212 Traditional method 2/2/2021 Topk Search(@ ICD E2013 12/42
Dynamic Programming 2/2/2021 TopkSearch @ ICDE2013 12/42 Di,j = min{Di-1, j + 1, Di, j-1 + 1, Di-1, j-1 + 0/1} Insertion Deletion Match/Subsitition
Dynamic Programming ●ED( sault, serajI)=2 sr a j i t 1|2|3|45 Dij=min Di-Li+1.D +I nsertee [2122345 a4|3|2 2 O if a where j5|432 lifa.≠b i654322 Delete t Traditional method 2/2/2021 Topk Search(@ ICD E2013
ED(srajit, seraji) = 2 Di,0 = i, D0,j = j, Di,j = min{Di-1, j + 1, Di, j-1 + 1, Di-1, j-1 + t i, j}, 0 if ai = bj 1 if ai bj . Dynamic Programming 2/2/2021 TopkSearch @ ICDE2013 13/42 where t i, j = Insert e Delete t
Outline ● Motivation ● Problem formulation e Progressive framework Pivotal Entry-based Method ● Range- based method ° Experiment ● Conclusion 2/2/2021 Topk Search(@ ICD E2013
Outline Motivation Problem Formulation Progressive Framework Pivotal Entry-based Method Range-based Method Experiment Conclusion 2/2/2021 TopkSearch @ ICDE2013 14/42
Progressive Method Smallest cell first 0123456 s r a i t o:(0,0)(1,1 0 01234 0 sera 56 2/2/2021 Topk Search(@ ICD E2013
Progressive Method 2/2/2021 TopkSearch @ ICDE2013 15/42 Smallest Cell First. E0 : (0, 0) (1,1)