search

ucrparlay / Edit-Distance

ESA'23: Efficient Parallel Output-Sensitive Edit Distance
MIT License
9 stars 1 forks source link

Accuracy for what level of edit distance #24

Open jianshu93 opened 2 months ago

jianshu93 commented 2 months ago

Hello Team,

Not sure to what level of edit distance, this parallel algorithm can still be accurate, say 1000 nt length.

Thanks,

Jianshu

Akatsukis commented 2 months ago

Hi Jiansu,

Thank you for your interest in our algorithms!

What do you mean by 1000nt length? If 1000nt means input sequences with length 1000, the scale might be too small for parallel algorithms.

Our BFS-SA can always produce the exact answer for any input. Our BFS-Hash or BFS-H-Hash algorithms can compute the correct output for reasonably large input sizes (say $10^9$, according to our experimental results).

Best, Xiaojun