Constructing target-aware results for keyword search on knowledge graphs

Existing work of processing keyword searches on graph data focuses on efficiency of result generation. However, being oblivious to user search intention, a query result may contain multiple instances of user search target, and multiple query results may contain information for the same instance of user search target. With the misalignment between query results and search targets, a ranking function is unable to effectively rank the instances of search targets. In this paper we propose the concept of target-aware query results driven by inferred user search intention. We leverage the Information Theory and develop a general probability model to infer search targets by analyzing return specifiers, modifiers, relatedness relationships, and query keywords' information gain. Then we propose two important properties for a target-aware result: atomicity and intactness. We develop techniques to efficiently generate target-aware results. Extensive experimental evaluation shows the effectiveness and efficiency of our approach.