Does preprocessing help in fast sequence comparisons?
Elazar Goldenberg, Aviad Rubinstein, Barna Saha · 2020
We study edit distance computation with preprocessing: the preprocessing algorithm acts on each string separately, and then the query algorithm takes as input the two preprocessed strings. This model is inspired by scenarios where we would like to compute edit distance between many pairs in the same pool of strings.