Does preprocessing help in fast sequence comparisons?

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.

Authors

• Elazar Goldenberg
• Aviad Rubinstein
• Barna Saha

Keywords

• preprocessing
• edit distance
• approximation algorithms