document: Efficient interactive fuzzy keyword search Traditional information systems return answers after a user submits a complete query . Users often feel `` left in the dark '' when they have limited knowledge about the underlying data , and have to use a try-and-see approach for finding information . A recent trend of supporting autocomplete in these systems is a first step towards solving this problem . In this paper , we study a new information-access paradigm , called `` interactive , fuzzy search , '' in which the system searches the underlying data `` on the fly '' as the user types in query keywords . It extends autocomplete interfaces by ( 1 ) allowing keywords to appear in multiple attributes ( in an arbitrary order ) of the underlying data ; and ( 2 ) finding relevant records that have keywords matching query keywords approximately . This framework allows users to explore data as they type , even in the presence of minor errors . We study research challenges in this framework for large amounts of data . Since each keystroke of the user could invoke a query on the backend , we need efficient algorithms to process each query within milliseconds . We develop various incremental-search algorithms using previously computed and cached results in order to achieve an interactive speed . We have deployed several real prototypes using these techniques . One of them has been deployed to support interactive search on the UC Irvine people directory , which has been used regularly and well received by users due to its friendly interface and high efficiency .
doc_bio_tags: O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O B O O O O O O O O O O O O O O O O O O O O O O O O O O O B I O O O O O O O O O O O O O O O O O O O O O O O O O B O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O B I O O O O O O O O O O O O O O O O O O O O O O O O O O