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.
|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|
Copyright in each Dissertation and Thesis is retained by the author. All Rights Reserved
The supplemental file or files you are about to download were provided to ProQuest by the author as part of a
dissertation or thesis. The supplemental files are provided "AS IS" without warranty. ProQuest is not responsible for the
content, format or impact on the supplemental file(s) on our system. in some cases, the file type may be unknown or
may be a .exe file. We recommend caution as you open such files.
Copyright of the original materials contained in the supplemental file is retained by the author and your access to the
supplemental files is subject to the ProQuest Terms and Conditions of use.
Depending on the size of the file(s) you are downloading, the system may take some time to download them. Please be