This tutorial provides a comprehensive overview of recent research progress on the important problem of approximate search in string collections. We identify existing indexes, search algorithms, filtering strategies, selectivity-estimation techniques and other work, and comment on their respective merits and limitations. Text data is ubiquitous. Management of string data in databases and information systems has taken on particular importance recently. This tutorial focuses on the following problem: Given a collection of strings, efficiently identify the ones similar to a given query string. Such a query is called an "approximate string search." This problem is of great interest for a variety of applications, as illustrated by the following examples. Data Cleaning: Information from multiple data sources often have numerous inconsistencies. For example, the same real-world entity can be represented in slightly different formats, such as "PO Box 23, Main St." and "P.O. Box 23, Main St". Errors can also be introduced due to irregularities in the data-collection process, from human mistakes, and many other causes. For these reasons, one of the main goals of data cleaning is to find similar entities within a collection, or all similar pairs of entities across a number of collections. Query Relaxation: Often enough, users might pose SQL queries to a DBMS that contain selection predicates that do not match all of the relevant data within the database exactly. The reasons are possible errors in the query, inconsistencies in the data, limited knowledge about the data, and more. By supporting query relaxation, the DBMS can return data of potential interest to the user, based on query predicate similarity (e.g., returning "Steven Spielberg" as an answer to the query "Steve Spielberg"). Spell Checking: Given an input document, a spell checker finds potential candidates for a possibly mistyped word by Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, to post on servers or to redistribute to lists, requires a fee and/or special permission from the publisher, ACM. VLDB '09, August 24-28, 2009, Lyon, France Copyright 2009 VLDB Endowment, ACM 000-0-00000-000-0/00/00. performing an approximate string search in its dictionary. Interactive Search: A very recent important application is to provide answers to query results in real-time, as users are typing their query (e.g., a Google search box with a dropdown suggestion menu that updates as users type). Such interactive-search boxes are ubiquitous and have shown to be very important in practice, because they limit the number of errors made by users and also reduce the number of query reformulations submitted in order to find the one that will yield satisfying results. The drawback of almost all existing, interactive techniques is that they support only prefix or substring matches, without regard for fuzzy, approximate searching; if users make a spelling mistake, they are presented with an empty suggestion box. One reason is that interactive approximate string search has attracted little attention and is not a trivial problem to solve, given the expensive nature of string similarity functions and ranking techniques. These applications require approximate-string-search algorithms with a high real-time performance. For instance, consider a spell checker such as those used by Gmail, Hotmail, or Yahoo! Mail, which need to be invoked numerous times per second, in order to support the millions of concurrent users using these services. Each spell checking request needs to be processed as fast as possible. Clearly, higher throughput allows the server to serve a much larger number of users seamlessly. Another example is a business search on a local-search engine (e.g., YellowPages, Yahoo! Local, and Superpages). It is very often the case that users misspell business names (e.g., "Wall-mart" instead of "Wal-mart"), and hence approximate string search in the context of localsearch is essential. Performing approximate string searching efficiently over the very large string collections present in these applications is fundamental in order to be able to sustain thousands of user requests per second. A closely related problem is that of selectivity estimation for approximate-string-matching queries. It is of great interest to be able to efficiently and accurately evaluate the selectivity of selection queries for the purpose of query optimization (in order to design efficient query-execution plans). Clearly, the selectivity of approximate string matching queries depends highly on the similarity function used. Hence, a variety of selectivity-estimation algorithms have already been proposed in the literature, for different similarity functions and based on a diverse number of techniques (e.g., histograms, sampling, and clustering).
Approximate string search has been extensively studied in the literature (please refer to an excellent tutorial REF and references therein).
Efficient Approximate Search on String Collections
PVLDB
PVLDB
Computer Science