Problem definition DEFINITION 1 (STRING SIMILARITY SEARCH). Given a string dataset R, a query string s, and an edit-distance thresh old T, the string similarity search with edit-distance con- straints finds all strings r ER such that ed(r,S)<T id string Query string lmyouteca s= yotubecom"andτ=2 r2 ubuntucom r3 utubbecou r4 youtbecom r5 yoytubeca ed(s, r4<=2 output ra as a result string dataset RProblem Definition Query string s = “yotubecom” and τ = 2 string dataset R ed(s, r4 ) <= 2 output r4 as a result