Query Suggestion Techniques For Keyword Search

Keyword Search is a classic and widely-accepted paradigm for querying the unstruc-tured text data (e.g., World Wide Web). This paradigm allows users to retrieve results withsimple keywords, releasing the burdens of learning query languages and understandingthe underlying data. Recently, because of its distinguished usability, keyword search hasbeen introduced to structured data, such as traditional relational databases and Deep Webdatabases. However, as the underlying data becomes more and more complex, the limita-tion of keyword search on the expressiveness becomes more and more obvious. Specifi-cally, since query keywords are inherently ambiguous and structure-free, keyword searchfails to accurately capture users’ query intent and cannot specify structure informationof the desired results. Thus, this simple query paradigm brings difculties to various re-trieval tasks on unstructured and structured data. To address this problem, this dissertationproposes efective query suggestion methods to help users efectively express their queryintent. The contributions of this dissertation are as follows.1. For unstructured text data, users may encounter difculties when formulating high-quality keyword queries. To address this problem, some existing methods suggest querykeywords based on simple statistic information, such as co-occurrence. This dissertationproposes a topic-based query suggestion method, which analyzes the topic informationbased on users’ inputs and suggests topically coherent keywords to help users expresstheir query intent. In addition, the dissertation also devises an instant suggestion algorith-m supporting autocompletion. As a user types in a prefix letter by letter, the algorithminstantly suggests keywords with the prefix. Obviously, this algorithm can allow users toselect or modify query keywords quickly, and thus improves the query efciency.2. For traditional relational databases, simple keyword queries cannot specify thestructure information of desired results. To address this problem, existing methods onkeyword search find joined tuples containing query keywords as results. They cannotprecisely capture users’ query intent and may involve irrelevant results. This dissertationproposes a novel search method, interactive SQL query suggestion, which combines theconvenience of keyword search and the power of SQL queries. While reducing the burdenof posing queries, the new method can interactively help users formulate SQL queries, even with advanced features, such as range queries, aggregation functions, efective joinpath, etc. To this end, this dissertation introduces efective ranking models and efcientalgorithms, which bridges the information gap between unstructured keyword queries andstructured data, leading to a more user-friendly and powerful query paradigm.3. For the Deep Web, the limited access permission of Web databases results inmore difculties to analyze users’ structural information needs. To address this problem,this dissertation proposes a keyword-based Deep Web database suggestion method. Usingnovel query log mining methods and database sampling techniques, the proposed methodcan efectively compute the relevance between keywords and Web databases, even if thedatabase accesses are limited. Therefore, the method bridges the gap between unstructuredkeyword queries and the hidden structured data, and thus seamlessly integrates query onDeep Web with existing search engines.