T.Batu; "A Sublinear Algorithm for Weakly Approximating Edit Distance"

A Sublinear Algorithm for Weakly Approximating Edit Distance
 

Tuğkan Batu
 

 Abstract:
 

We show how to determine whether the edit distance between two given strings is small in sub linear 

time. Specifically, we present a test which, given two n-character strings A and B, runs in time o(n) 

and with high probability returns ``CLOSE'' if their edit distance is O(n^a)$, and "FAR" if their edit 

distance is Omega(n), where "a" is a fixed parameter less than 1.  Our algorithm for testing the edit 

distance works by recursively subdividing the strings A and B into smaller substrings and looking 

for pairs of  substrings in A, B with small edit distance.  To do this, we query both strings at random 

places using a special technique for economizing on the samples which does not pick the samples 

independently and provides better query and overall complexity.
 

Short Bio:
 

Tugkan Batu received his BS degree in Computer Science from Bilkent University and his 

PhD in Computer Science from Cornell University. He did post-doctoral work at University of 

Texas at Austin and is now a post-doc at Simon Fraser University in Canada. His home page is
 

http://www.cs.sfu.ca/~batu/personal/
 

December 16, 2004, 14:40 - 15:30,  FENS G015