Diversified Top-k Keyword Query Interpretation on Knowledge Graphs

Exploring a knowledge graph through keyword queries to discover meaningful patterns has been studied in many scenarios recently. From the perspective of query understanding, it aims to find a number of specific interpretations for ambiguous keyword queries. With the assistance of interpretation, the users can actively reduce the search space and get more relevant results. In this paper, we propose a novel diversified top-k keyword query interpretation approach on knowledge graphs. Our approach focuses on reducing the redundancy of returned results, namely, enriching the semantics covered by the results. In detail, we (1) formulate a diversified top-k search problem on a schema graph of knowledge graph for keyword query interpretation; (2) define an effective similarity measure to evaluate the semantic similarity between search results; (3) present an efficient search algorithm that guarantees to return the exact top-k results and minimize the calculation of similarity, and (4) propose effective pruning strategies to optimize the search algorithm. The experimental results show that our approach improves the diversity of top-k results significantly from the perspectives of both statistics and human cognition. Furthermore, with very limited loss of result precision, our optimization methods can improve the search efficiency greatly.