Effective Keyword Search in Graphs

Keyword search in node-labeled graphs finds subtrees of the graph whose nodes contain all of the input keywords. Previous work ranks answer trees using combinations of structural and content-based metrics, such as path lengths between keywords or relevance of the labels in the answer tree to the query keywords. We propose two new ways to rank keyword search results over graphs. The first takes node importance into account while the second is a bi-objective optimization of edge weights and node importance. Since both of these problems are NP-hard, we propose greedy algorithms to solve them, and experimentally verify their effectiveness and efficiency on a real dataset.