Approximate/Fuzzy Search for strings keys
Date: Thu, 19 Jun 2008 09:36:57 -0700 (PDT)
Message-ID: <a3dd0b45-2946-4eee-8248-7072a48a8b76_at_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 - 18:36:57 CEST