
Type: Improvement

Status: Closed

Priority: Minor

Resolution: Fixed

Affects Version/s: None

Fix Version/s: None

Component/s: None

Labels:None
Local optimization of the current editdistance handling code in AsterixDB: Can we terminate the edit distance calculation based on a given editdistance threshold T? I think the answer is yes.
Basic Algorithm:
For two strings X and Y,
Init:
Construct D(len(X)+1=M, len(Y)+1=N).
D(i,0) = i
D(j,0) = j
Iteration:
For each i = 1 to M For each j = 1 to N D(i,j) = min( D(i1,j) + 1 // deletion case D(i,j1) + 1 // insertion case D(i1,j1) + cost (cost is 2 if X(i) != Y(j), cost is 0 if X(i) = Y(j)) )
Result:
D(M,N) is the edit distance value.
Example:
Early Termination condition:
So, for the given threshold T, we can stop the computation early if the values of three cases are greater than T. That is,
min (D(i1,j), D(i,j1), D(i1,j1)) > T
This holds since if the cost of all possible cases (insertion, deletion, and substitution) is greater than T, all future operations will be greater than T in any cases.