Survey on Type-ahead search

Abstract

A search-as-you-type system calculates answers on the fly as a user types in a keyword query character by character. We want to study how to support search as you type on data residing in a relational DBMS. We concentrate on how to support this type of search using the native database language and SQL. A main task that tests is how to leverage existing database functionalities to meet the high performance requirement to achieve an interactive speed. We studied how to use auxiliary indexes stored as tables to increase search performance. We presented solutions for both single keyword queries and multi keyword queries and developed novel techniques for fuzzy search using SQL by allowing mismatches between query keywords and answers. We extended the techniques to the case of fuzzy queries, and proposed various techniques to improve query performance. We proposed incremental computation techniques to answer multi keyword queries, and studied how to support first N queries and incremental updates. Our experimental results on large and real data sets showed that the proposed techniques can enables DBMS systems to support search as you type on large tables.