An effective suggestion method for keyword search of databases

Hai Huang, Zonghai Chen, Chengfei Liu, He Huang, Xiangliang Zhang

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

This paper solves the problem of providing high-quality suggestions for user keyword queries over databases. With the assumption that the returned suggestions are independent, existing query suggestion methods over databases score candidate suggestions individually and return the top-k best of them. However, the top-k suggestions have high redundancy with respect to the topics. To provide informative suggestions, the returned k suggestions are expected to be diverse, i.e., maximizing the relevance to the user query and the diversity with respect to topics that the user might be interested in simultaneously. In this paper, an objective function considering both factors is defined for evaluating a suggestion set. We show that maximizing the objective function is a submodular function maximization problem subject to n matroid constraints, which is an NP-hard problem. An greedy approximate algorithm with an approximation ratio O((Formula presented.)) is also proposed. Experimental results show that our suggestion outperforms other methods on providing relevant and diverse suggestions. © 2016 Springer Science+Business Media New York
Original languageEnglish (US)
Pages (from-to)729-747
Number of pages19
JournalWorld Wide Web
Volume20
Issue number4
DOIs
StatePublished - Sep 9 2016

Fingerprint Dive into the research topics of 'An effective suggestion method for keyword search of databases'. Together they form a unique fingerprint.

Cite this