The ObjectRank system applies the random walk model, the effectiveness of which is proven by Google, to keyword search in databases modeled as labeled graphs. The system ranks the database objects with respect to the user-provided keywords. Conceptually, random walks start from the objects containing the keywords. Each object is ranked with respect to the particular keywords, based on the stationary probability that random walks are found at the object at a given time. Appropriate AND and OR semantics are presented, which consider the different role of the graph edges and avoid the (more common than in Google's PageRank and the Web) "rank sink" problem. Two sets of novel performance challenges and opportunities are addressed. First, schemas (potentially augmented with simple annotations) impose constraints on the graph, which are exploited for performance purposes. Second, instead of a global PageRank, we efficiently compute multiple keyword specific ObjectRanks ,which are then combined efficiently in order to produce the top-k objects. We performed a user survey and a set of performance experiments on the DBLP dataset, which show that our approach is semantically meaningful and feasible to implement respectively.
Demo (jsp interface by Michael Sirivianos)