| 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. The trend of supporting autocomplete in these systems is a first step towards solving this problem. A new information-access paradigm, called instant search (a.k.a. interactive search or type-ahead search) searches the underlying data "on the fly" as the user types in query keywords. A recent well-known example of instant search is Google Instant introduced in September 2010. This revolutionary framework, which allows users to explore data as they type, even in the presence of minor errors, greatly improves user search experiences. This dissertation studies research challenges in this framework for large amounts of data. Since each keystroke of the user could invoke a query on the back end, efficient algorithms are needed to process each query very efficiently (e.g., within milliseconds). We develop various algorithms for answering both single-keyword queries and multi-keyword queries, using previously computed and cached results in order to achieve a high instant speed. We develop techniques that reduce the memory requirements of instant-search systems using solid-state drives. We also study instant search on multiple tables in a relational database, where the system returns relevant records that together answer the query. Last but not least, we study location-based instant search, which searches for geographical records that satisfy both keyword and spatial conditions. We developed multiple prototypes to demonstrate our techniques, such as the UCI people search facility and the iPubmed search system. We also conducted extensive experiments to prove the efficiency of our techniques. |
