Dissertation/Thesis Abstract

Efficient Instant Search
by Ji, Shengyue, Ph.D., University of California, Irvine, 2011, 153; 3439506
Abstract (Summary)

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.

Indexing (document details)
Advisor: Li, Chen
Commitee: Carey, Michael J., Jain, Ramesh, Mehrotra, Sharad
School: University of California, Irvine
Department: Information and Computer Science - Ph.D.
School Location: United States -- California
Source: DAI-B 72/03, Dissertation Abstracts International
Subjects: Information Technology, Computer science
Keywords: Autocompletion, Instant searching, Search engines, Web searches
Publication Number: 3439506
ISBN: 978-1-124-44682-0
Copyright © 2020 ProQuest LLC. All rights reserved. Terms and Conditions Privacy Policy Cookie Policy