Re: Approximate String Matching in RDBMS
Date: Thu, 20 Jan 2011 08:57:45 -0800 (PST)
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
> 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