Re: Approximate String Matching in RDBMS

On Jan 19, 5:07 pm, PRAGMATECH <walid.s..._at_gmail.com> wrote:
> Dear All,
>
> Does someone know what is the best theoretical complexity in the
> literature, as O(f(N)), where N is the number of rows in a table t
> and
> where approximate string matching on some field in t is to be done.
>
> I am not asking about the complexity of a single approximate match
> between 2 strings with lengths n and m, but on the cost of the lookup
> over the entire table.
> In other words, what is the cost of the following, in terms of N, the
> number of rows in t:
>
> SELECT * FROM t WHERE APPROXIMATELY_EQUAL(t.a, threshold)
>
> I thank you in advance for any feedback.
>
> Best Regards,
> Walid Saba

While looking into your question, I came across this: http://blog.notdot.net/2010/07/Damn-Cool-Algorithms-Levenshtein-Automata

I didn't see the answer to your question, but I hope this helps. Received on Thu Jan 20 2011 - 17:57:45 CET