EfficientApproximateSearchonStringCollections(Tutorial)Marios Hadjieleftheriou Chen LiAT&T Labs–Research UC Irvine180 Park Ave Bldg 102 Bren Hall, Room 2092Florham Park NJ 07932 Irvine CA 92697Phone:+19733607082, Fax:+19733608077 Phone:+19498249470, Fax:+9498244056marioh@research.att.com chenli@ics.uci.eduABSTRACT performing an approximate string search in its dictionary.Interactive Search: A very recent important application isThis tutorial provides a comprehensive overview of recentto provide answers to query results in real-time, as users areresearch progress on the important problem of approximatetyping their query (e.g., a Google search box with a drop-search in string collections. We identify existing indexes,down suggestion menu that updates as users type). Suchsearch algorithms, filtering strategies, selectivity-estimationinteractive-search boxes are ubiquitous and have shown totechniquesandotherwork, andcommentontheirrespectivebe very important in practice, because they limit the num-merits and limitations.ber of errors made by users and also reduce the number1. MOTIVATION of query reformulations submitted in order to find the oneText data is ubiquitous. Management of string data in that will yield satisfying results. The drawback of almostdatabases and information systems has taken on particular all existing, interactive techniques is that they support onlyimportance recently. This tutorial focuses on the following prefix or substring ...
Voir