Improving the Effectiveness of Keyword Search in Databases Using Query Logs

Using query logs to enhance user experience has been extensively studied in the Web IR literature. However, in the area of keyword search on structured data (relational databases in particular), most existing work has focused on improving search result quality through designing better scoring functions, without giving explicit consideration to query logs. Our work presented in this paper taps into the wealth of information contained in query logs, and aims to enhance the search effectiveness by explicitly taking into account the log information when ranking the query results. To concretize our discussion, we focus on schema-graph-based approaches to keyword search (using the seminal work DISCOVER as an example), which usually proceed in two stages, candidate network (

CN

) generation and

CN

evaluation. We propose a query-log-aware ranking strategy that uses the frequent patterns mined from query logs to help rank the

CN

s generated during the first stage. Given the frequent patterns, we show how to compute the maximal score of a

CN

using a dynamic programming algorithm. We prove that the problem of finding the maximal score is NP-hard. User studies on a real dataset validate the effectiveness of the proposed ranking strategy.