Approximate/Fuzzy Search for strings keys

From: <walid.saba_at_gmail.com>
Date: Thu, 19 Jun 2008 09:36:57 -0700 (PDT)
Message-ID: <a3dd0b45-2946-4eee-8248-7072a48a8b76@f24g2000prh.googlegroups.com>


Dear all,

I have read the literature on fuzzy/approximate search for strings keys in large databases, but I could not find a clear answer on what is the best that has been achieved thus far in terms of the cost of search (regardless of cost of building any index).

I understand this depends on the application/domain/type of data, but, to keep things simple, supoose the target data is some string (names, addresses, or any sequence of characters), and assume any distance function. I am simply asking this: what is the best that has been achieved? Is there a logarithmic solution (i.e., that can retrieve a set of "similar" objects in some logarithmic order), or are they all, in the worst case, linear?

I thank you in advance... Received on Thu Jun 19 2008 - 11:36:57 CDT

Original text of this message