Re: Approximate String Matching in RDBMS

From: Nilone <reaanb_at_gmail.com>
Date: Thu, 20 Jan 2011 08:57:45 -0800 (PST)
Message-ID: <5f7e8697-ee17-4763-9275-d2a7b7eadfc3_at_j1g2000vbl.googlegroups.com>



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 - 10:57:45 CST

Original text of this message